Greedy Strikes Back: Improved Facility Location Algorithms

M. L. Balinski, On finding integer solution to linear programs, in, Proc. of the IBM Scientific Computing Symposium on Combinatorial Problems, 1966, 225, 248

Cornuejols, 1990, The uncapacitated facility location problem

Chudak, 1998, Improved approximation algorithms for uncapacitated facility location, 1412

U. Feige, A threshold of lnn, in, 28th ACM Symposium on Theory of Computing, 1996, 314, 318

J. Håstad, Some optimal inapproximability results, in, 29th ACM Symposium on Theory of Computing, 1997, 1, 10

Hochbaum, 1982, Heuristics for the fixed cost median problem, Math. Programming, 22, 148, 10.1007/BF01581035

Hochbaum, 1996

M. Korupolu, C. G. Plaxton, R. Rajaraman, Analysis of a local search heuristic for facility location problems, in, 9th ACM-SIAM Annual Symposium on Discrete Algorithms, 1998, 1, 10

Kuehn, 1963, A heuristic program for locating warehouses, Manag. Sci., 9, 643, 10.1287/mnsc.9.4.643

Lin, 1992, Approximation algorithms for geometric median problems, Inform. Process. Lett., 44, 245, 10.1016/0020-0190(92)90208-D

Lund, 1994, On the hardness of approximating minimization problems, Assoc. Comput. Mach., 41, 960, 10.1145/185675.306789

Manne, 1964, Plant location under economies-of-scale-decentralization and computation, Manage. Sci., 11, 213, 10.1287/mnsc.11.2.213

Mirzain, 1985, Langrangian relaxation for the star-star concentrator location problem, Networks, 15, 1, 10.1002/net.3230150102

Mulvey, 1979, Cluster analysis: An application of Lagrangian relaxation, Manage. Sci., 25, 329, 10.1287/mnsc.25.4.329

Papadimitriou, 1991, Optimization, approximation, and complexity classes, J. Comput. System Sci., 43, 425, 10.1016/0022-0000(91)90023-X

D. Shmoys, E. Tardos, K. Aardal, Approximation algorithms for facility location problems, in, 29th ACM Symposium on Theory of Computing, 1997, 265, 274

Stollsteimer, 1963, A working model for plant numbers and locations, J. Farm Econom., 45, 631, 10.2307/1235442