Near-optimal solutions to large-scale facility location problems

Aardal, 1998, Capacitated facility location, Math. Programming, 81, 149, 10.1007/BF01581103 Ahn, 1988, Probabilistic analysis of a relaxation for the k-median problem, Math. Oper. Res., 13, 1, 10.1287/moor.13.1.1 Balinski, 1965, Integer programming, Management Sci., 12, 253, 10.1287/mnsc.12.3.253 Barahona, 2000, The volume algorithm, Math. Programming, 87, 385, 10.1007/s101070050002 F.A. Chudak, Improved approximation algorithms for the uncapacitated facility location problem, Ph.D. Thesis, Cornell University, 1998. Chudak, 1998, Improved approximation algorithms for uncapacitated facility location, 180 F.A. Chudak, D.B. Shmoys, Improved approximation algorithms for the uncapacitated facility location problem, SIAM J. Comput. 33 (2003) 1, 1–25. Cornuéjols, 1990, The uncapacitated facility location problem, 119 Cornuéjols, 1991, A comparison of heuristics and relaxations for the capacitated plant location problem, European J. Oper. Res., 50, 280, 10.1016/0377-2217(91)90261-S Erlenkotter, 1978, A dual-based procedure for uncapacitated facility location, Oper. Res., 26, 992, 10.1287/opre.26.6.992 D. Erlenkotter, Program DUALOC—Version II, Distributed on request, 1991. A.V. Goldberg, An efficient implementation of a scaling minimum-cost flow algorithm, Technical Report STAN-CS-92-1439, Stanford University, 1992. Held, 1991, Validation of subgradient optimization, Math. Programming, 49, 62 C. Lemaréchal, Nondifferential optimization, in: G.L. Nemhauser, A.H.G. Rinnoy Kan, M.J. Todd (Eds.), Optimization, Handbooks in Operations Research, North Holland, Amsterdam, 1989, pp. 529–572. P. Mirchandani, R. Francis (Eds.), Discrete Location Theory, Wiley, New York, 1990. Raghavan, 1987, Randomized rounding, Combinatorica, 7, 365, 10.1007/BF02579324 D.B. Shmoys, É. Tardos, K. Aardal, Approximation algorithms for facility location problems, in: Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 265–274. Wolfe, 1975, A method of conjugate subgradients for minimizing nondifferentiable functions, Math. Programming Study, 3, 145, 10.1007/BFb0120703