
[1] Agarwal, P. K. and Procopiuc, C. M., "Exact and approximation algorithms for clustering," Algorithmica, vol. 33, 201226, 2002. [2] Agarwal, P. K. and Sharir, M., "Efficient algorithms for geometric optimization," ACM Computing Surveys, vol. 30, no. 4, 412458, 1998. [3] Alstrup, S., Lauridsen, P. W., Sommerlund, P., and Thorup, M., "Finding cores of limited length," Technical Report, the IT University of Copenhagen, 2001. (A preliminary version appeared in Proceedings of the 5th International Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, vol. 1272, pp. 4554, 1997.) [4] Andreatta, G. and Mason, F. M., "keccentricity and absolute kcentrum of a tree," European Journal of Operational Research, vol. 19, 114117, 1985. [5] Andreatta, G. and Mason, F. M., "Properties of the kcentrum in a network," Networks, vol. 15, 2125, 1985. [6] Arora, S., Raghavan, P., and Rao, S., "Approximation schemes for Euclidean kmedian and related problems," In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, ACM, New York, 106113, 1998. [7] Averbakh, I., "Minmax regret solutions for minimax optimization problems with uncertainty," Operations Research Letters, vol. 27, no. 2, 5765, 2000. [8] Averbakh, I., "Complexity of robust singlefacility location problems on networks with uncertain lengths of edges," Discrete Applied Mathematics, vol. 127, no. 3, 505522, 2003. [9] Averbakh, I., "The minimax relative regret median problem on networks," INFORMS Journal on Computing, vol. 17, no. 4, 451461, 2005. [10] Averbakh, I. and Bereg, S., "Facility location problems with uncertainty on the plane," Discrete Optimization, vol. 2, no. 1, 334, 2005. [11] Averbakh, I. and Berman, O., "Minimax regret pcenter location on a network with demand uncertainty," Location Science, vol. 5, no. 4, 247254, 1997. [12] Averbakh, I. and Berman, O., "Algorithms for the robust 1center problem on a tree," European Journal of Operational Research, vol. 123, no. 2, 292302, 2000. [13] Averbakh, I. and Berman, O., "Minmax regret median location on a network under uncertainty," Informs Journal on Computing, vol. 12, no. 2, 104110, 2000. [14] Averbakh, I. and Berman, O., "An improved algorithm for the minmax regret median problem on a tree," Networks, vol. 41, no. 2, 97103, 2003. [15] BenMoshe, B., Bhattacharya, B. K., and Shi, Q., "An optimal algorithm for the continuous/discrete weighted 2center problems in trees," in Proceedings of the 7th Latin American Theoretical Informatics Symposium, Lecture Notes on Computer Science, vol. 3887, 166177, 2006. [16] Brodal, G., Georgiadis, L., and Katriel, I., "An O(n log n) version of the AverbakhBerman algorithm for the robust median of a tree," Operations Research Letters, vol. 36, no. 1, 1418, 2008. [17] Burkard, R. E. and Dollani, H., "A note on the robust 1center problem on trees," Annals of Operations Research, vol. 110, no. 1, 6982, 2002. [18] Burkard, R. E. and Dollani, H., "Robust location problems with pos/neg weights on a tree," Networks, vol. 38, no. 2, 102113, 2001. [19] Burkard, R. E., Dollani, H., Lin, Y., and Rote, G., "The obnoxious center problem on a tree," SIAM Journal on Discrete Mathematics, vol. 14, no. 4, 498509, 2001. [20] Cappanera P, "A survey on obnoxious facility location problems," Technical Report, TR9911, Dipartimento di Informatica, Universita di Pisa, 1999. [21] Carrizosa, E. J., Conde, E., Fern�鴨dez, F. R., and Puerto, J., "An axiomatic approach to the centdian criterion," Location Science, vol. 3, 17, 1994. [22] Charikar, M., Chekuri, C., Goel, A., and Guha, S., "Rounding via trees: deterministic approximation algorithms for group steiner trees and kmedian," in Proceedings of the 30th ACM Symposium on Theory of Computing, ACM, New York, 114123, 1998. [23] Charikar, M., Guha, S., Tardos, ��, and Shmoys, D. B., "A constantfactor approximation algorithm for the kmedian problem," Journal of Computer and System Sciences, vol. 65, no. 1, 129149, 2002. [24] Chen, B. and Lin, C.S., "Minmaxregret robust 1median location on a tree," Networks, vol. 31, no. 2, 93103, 1998. [25] Church R. L. and Garfinkel R. S., "Locating an obnoxious facility on a network," Transportation Science, vol. 12, 107118, 1978. [26] Cole, R., "Slowing down sorting networks to obtain faster sorting algorithms," Journal of the ACM, vol. 34, 200208, 1987. [27] Conde, E., "A note on the minmax regret centdian location on trees," Operations Research Letters, vol. 36, no. 2, 271275, 2008. [28] Conde, E., "Minmax regret locationallocation problem on a network under uncertainty," European Journal of Operational Research, vol. 179, no. 3, 10251039, 2007. [29] Daskin, M. S., Network and discrete location: models, algorithms, and applications, Wiley, New York, 1995. [30] Drezner, Z., Facility location. A survey of applications and methods, Springer, New York, 1995. [31] Drezner, Z., "Sensitivity analysis of the optimal location of a facility," Naval Research Logistics Quarterly, vol. 33, 209224, 1980. [32] Drezner, Z. and Hamacher, H. W., Facility location: applications and theory, SpringerVerlag, New York, 2002. [33] Drezner, Z. and Wesolowsky, G. O., "Location of multiple obnoxious facilities," Transportation Science, vol. 19, 193202, 1985. [34] Dyer, M. E., "On a multidimensional search technique and its application to the Euclidean onecentre problem," SIAM Journal on Computing, vol. 15, 725738, 1986. [35] Fern�鴨dez, F. R., Nickel, S., Puerto, J., and Rodr�櫂uezCh�朦, A. M., "Robustness in the Paretosolutions for the multicriteria minisum location problem," Journal of Multicriteria Decision Analysis, vol. 10, no. 4, 191203, 2001. [36] Francis, R. L., Lowe, T. J., and Tamir, A., "Aggregation error bounds for a class of location models," Operations Research, vol. 48, 294–307, 2000. [37] Frank, H., "Optimum locations on a graph with probabilistic demands," Operations Research, vol. 14, 409421, 1966. [38] Frank, H., "Optimum locations on a graph with correlated normal demands," Operations Research, vol. 14, 552557, 1967. [39] Frederickson, G. N., "Optimal parametric search algorithms in trees II: pcenter problems and check points," Technical Report, Purdue University, 1992. [40] Frederickson, G. N. and Johnson, D. B., "Finding kth paths and pcenters by generating and searching good data structures," Journal of Algorithms, vol. 4, pp. 6180, 1983. [41] Gabow, H. N. and Tarjan, R. E., "A lineartime algorithm for a special case of disjoint set union," Journal of Computer and System Sciences, vol. 30, no. 2, 209221, 1985. [42] Gavish, B. and Sridhar, S., "Computing the 2median on tree networks in O(n log n) time," Networks, vol. 26, 305317, 1995. [43] Goldman, A. J., "Optimal center location in simple networks," Transportation Science, vol. 5, 212221, 1971. [44] Hakimi, S. L., "Optimal locations of switching centers and the absolute centers and medians of a graph," Operations Research, vol. 12, 450459, 1964. [45] Halpern, J., "The location of a centdian convex combination on an undirected tree," Journal of Regional Science, vol. 16, 237245, 1976. [46] Halpern, J., "Finding minimal centermedian convex combination (centdian) of a graph," Management Science, vol. 24, no. 5, 535547, 1978. [47] Halpern, J., "Duality in the centdian of a graph," Operations Research, vol. 28, 722735, 1980. [48] Hsu, W. L., "The distancedomination numbers of trees," Operations Research Letters, vol. 1, 96100, 1982. [49] Hwang, R. Z., Lee, R. C. T., and Chang, R. C., "The searching over separators strategy to solve some NPhard problems in subexponential time," Algorithmica, vol. 9, 398423, 1993. [50] Hwang, R. Z., Lee, R. C. T., and Chang, R. C., "The slab dividing approach to solve the Euclidean pcenter problem," Algorithmica, vol. 9, 122, 1993. [51] Jain, K. and Vazirani, V. V., "Approximation algorithms for metric facility location and kMedian problems using the primaldual schema and Lagrangian relaxation," Journal of the ACM, vol. 48, no. 2, 274296, 2001. [52] Kalcsics, J., Nickel, S., Puerto, J., and Tamir, A., "Algorithmic results for ordered median problems defined on networks and the plane," Operations Research Letters, vol. 30, 149158, 2002. [53] Kariv, O. and Hakimi, S. L., "An algorithmic approach to network location problems. I: The pcenters," SIAM Journal on Applied Mathematics, vol. 37, no. 3, 513538, 1979. [54] Kariv, O. and Hakimi, S. L., "An algorithmic approach to network location problems. II: The pmedians," SIAM Journal on Applied Mathematics, vol. 37, no. 3, 539560, 1979. [55] Kouvelis, P., Vairaktarakis, G., and Yu, G., "Robust 1median location on a tree in the presence of demand and transportation cost uncertainty," Working Paper 93/9434, Department of Management Science and Information Systems, Graduate School of Business, The University of Texas at Austin, 1994. [56] Kouvelis, P. and Yu, G., Robust discrete optimization and its applications, Kluwer Academic Publishers, Dordrecht, 1997. [57] Ku, S.C., Lu, C.J., Wang, B.F., and Lin, T.C., "Efficient algorithms for two generalized 2median problems on trees," in Proceedings of the 12th International Symposium on Algorithms and Computation, Lecture Notes on Computer Science, vol. 2223, 768778, 2001. [58] Labb��, M., Peeters, D., and Thisse, J.F., "Location on networks," in Handbooks in OR & MS, vol. 8, Ball, M. O., editors, Elsevier, Amsterdam, 1995. [59] Labb��, M., Thisse, J.F., and Wendell, R., "Sensitivity analysis in minisum facility location problems," Operations Research, vol. 38, 961969, 1991. [60] Megiddo, N., "Lineartime algorithms for linearprogramming in R3 and related problems," SIAM Journal on Computing, vol. 12, no. 4, 759776, 1983. [61] Megiddo, N. and Supowit, K. J., "On the complexity of some common geometric location problems," SIAM Journal on Computing, vol. 13, 182196, 1984. [62] Megiddo, N. and Tamir, A., "New results on the complexity of pcenter problems," SIAM Journal on Computing, vol. 12, no. 4, 751758, 1983. [63] Megiddo, M., Tamir, A., Zemel, E., and Chandrasekaran, R., "An O(n log2 n) algorithm for the kth longest path in a tree with applications to location problems," SIAM Journal on Computing, vol. 10, no. 2, 328337, 1981. [64] Minieka, E., "Anticenters and antimedians of a network," Networks, vol. 13, 359364, 1983. [65] Mirchandani P. B. and Francis R. L., Discrete location theory, Wiley, New York, 1990. [66] Mirchandani, P. B. and Odoni, A. R., "Location of medians on stochastic networks," Transportation Science, vol. 13, 8597, 1979. [67] Mirchandani, P. B., Oudjit, A., and Wong, R. T., "Multidimensional extensions and a nested dual approach for the Mmedian problem," European Journal of Operational Research, vol. 21, 121137, 1985. [68] Nickel, S., "Discrete ordered Weber problems," In Operations Research Proceedings 2000, Fleischmann, B., Lasch, R., Derigs, U., Domschke, W., and Rieder, U., editors, Springer, Berlin, 71–76, 2001. [69] Nickel, S. and Puerto, J., "A unified approach to network location problems," Networks, vol. 34, 283290, 1999. [70] Nickel, S. and Puerto, J., Location Theory: A unified approach, SpringerVerlag, Heidelberg, Germany, 2005. [71] Nikulin, Y., "Robustness in combinatorial optimization and scheduling theory: an annotated bibliography," http://www.optimizationonline.org/DB_HTML/ 2004/11/995.html, 2004. [72] Oudjit, A., "Median locations on deterministic and probabilistic multidimensional networks," PhD Dissertation, Rennselaer Polytechnic Institute, Troy, 1981. [73] P�臆ezBrito, D. and MorenoP�臆ez, J. A., "The generalized pcentdian on network," Top, vol. 8, no. 2, 265285, 2000. [74] Puerto, J. and Rodr�櫂uezCh�朦, A. M., "Robust positioning of service units," Stochastic Models, vol. 19, no. 1, 125147, 2003. [75] Puerto, J., Rodr�櫂uezCh�朦, A. M., and Tamir, A., "New results on minimax regret single facility ordered median location problems on networks," in Proceedings of the 15th Annual European Symposium on Algorithms, Lecture Notes on Computer Science, vol. 4698, 230240, 2007. [76] Rodr�櫂uezCh�朦, A. M., Nickel, S., Puerto, J. and Fern�鴨dez, F. R., "A flexible approach to location problems," Mathematical Methods of Operations Research, vol. 51, no. 1, 6989, 2000. [77] Slater, P. J., "Centers to centroids in a graph," Journal of Graph Theory, vol. 2, 209222, 1978. [78] Synder, L., "Facility location under uncertainty: A review," IIE Transactions, vol. 38, no. 7, 547564, 2006. [79] Tamir, A., "An O(pn2) time algorithm for the pmedian and related problems on tree graphs," Operations Research Letters, vol.19, no. 2, pp. 5964, 1996. [80] Tamir, A., "Improved complexity bounds for center location problems on network by using dynamic data structures," SIAM Journal on Discrete Mathematics, vol. 1, no. 3, 377396, 1988. [81] Tamir, A., "Obnoxious facility location on graphs," SIAM Journal on Discrete Mathematics, vol. 4, no. 4, 550567, 1991. [82] Tamir, A., "The kcentrum multifacility location problem," Discrete Applied Mathematics, vol. 109, 293307, 2001. [83] Ting, S. S., "A linear time algorithm for maxisum facility location on tree networks," Transportation Science, vol. 18, 7684, 1984. [84] Tamir, A., P�臆ezBrito, D., and MorenoP�臆ez, J. A., "A polynomial algorithm for the pcentdian problem on a tree," Networks, vol. 32, 255262, 1998. [85] Wang, B.F., Ku, S.C., and Shi, K.H., "Costoptimal parallel algorithms for the tree bisector and related problems," IEEE Transactions on Parallel and Distributed Systems, vol. 12, no. 9, 888898, 2001. [86] Weaver, J. R. and Church, R. L., "Computational procedures of location problems on stochastic networks," Transportation Science, vol. 17, 168180, 1983. [87] Vairaktarakis, G. L. and Kouvelis, P., "Incorporation dynamic aspects and uncertainty in 1median location problems," Naval Research Logistics, vol. 46, 147168, 1999. [88] Yu, H.Y. and Wang, B.F., "An improved algorithm for finding kcentrums on weighted trees," in Proceedings of the 9th International Conference on Parallel and Distributed Systems, 222225, 2002.
