Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation

Abstract

We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is their low running time: O(m logm) and O(m logm(L + log (n))) respectively, where n and m are the total number of vertices and edges in the underlying complete bipartite graph on cities and facilities. The main algorithmic ideas are a new extension of the primal-dual schema and the use of Lagrangian relaxation to derive approximation algorithms.

References

1. AGRAWAL, A., KLEIN, P., AND RAVI, R. 1995. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput. 24, 440-456.]]
2. ARORA, S., RAGHAVAN, P., AND RAO, S. 1998. Approximation schemes for Euclidean k-medians and related problems. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (Dallas, Tex., May 23-26). ACM, New York, pp. 106-113.]]
3. BALINSKI, M. L. 1966. On finding integer solutions to linear programs. In Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems. IBM, New York, pp. 225-248.]]
4. BARTAL, Y. 1996. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 184-193.]]
5. BAR-YEHUDA, R., AND EVEN, S. 1981. A linear time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2, 198-203.]]
6. BRADLEY,P.S.,FAYYAD,U.M.,AND MANGASARIAN, O. L. 1998. Mathematical programming for data mining: Formulations and challenges. Microsoft Technical Report, January.]]
7. CHARIKAR, M., CHEKURI, C., GOEL, A., AND GUHA, S. 1998. Rounding via trees: Deterministic approximation algorithms for group Steiner trees and k-median. In Proceedings of the 30th ACM Symposium on Theory of Computing (Dallas, Tex., May 23-26). ACM, New York, pp. 114-123.]]
8. CHARIKAR, M., AND GUHA, S. 1999. Improved combinatorial algorithms for the facility location and k-median problems. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 378-388.]]
9. CHARIKAR, M., GUHA, S., TARDOS, E., AND SHMOYS, D. B. 1999. A constant-factor approximation algorithm for the k-median problem. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing (Atlanta, Ga., May 1-4). ACM, New York, pp. 1-10.]]
10. CHARIKAR, M., KHULLER, S., MOUNT,D.M.,AND NARSHIMHAN, G. 2001. Algorithms for facility location problems with outliers. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 642-651.]]
11. CHUDAK, F. 1998. Improved approximation algorithms for uncapacitated facility location. In Integer Programming and Combinatorial Optimization, R. E. Bixby, E. A. Boyd, and R. Z. Rios-Mercado, eds. Lecture Notes in Computer Science; vol. 1412. Springer-Verlag, New York, pp. 180-194.]]
12. CHUDAK, F., AND SHMOYS, D. 1998. Improved approximation algorithms for the uncapacitated facility location problem. Unpublished manuscript.]]
13. CHUDAK, F., AND SHMOYS, D. 1999. Improved approximation algorithms for the capacitated facility location problem. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, Md., Jan. 17-19). ACM, New York, pp. S875-S876.]]
14. CHUDAK,F.A.,AND WILLIAMSON, D. P. 1999. Improved approximation algorithms for capacitated facility location problems. In Proceedings of the Integer Programming and Combinatorial Optimization.]]
15. CORNUEJOLS, G., NEMHAUSER,G.L.,AND WOLSEY, L. A. 1990. The uncapacitated facility location problem. In Discrete Location Theory. P. Mirchandani and R. Francis, eds. Wiley, New York, pp. 119-171.]]
16. DRINEAS, P., FRIEZE, A., KANNAN, R., VEMPALA, S., AND VINAY, V. 1999. Clustering in large graphs and matrices. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, Md., Jan. 17-19). ACM, New York, pp. 291-299.]]
17. EDMONDS, J. 1965. Maximum matching and a polyhedron with 0,1-vertices. J. Res. NBS B 69B, 125-130.]]
18. GARG, N. 1996. A 3-approximation for the minimum tree spanning k-vertices. In Proceedings of the 37th Annual IEEE Symposium on Foundation of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 302-309.]]
19. GARG, N., VAZIRANI, V., AND YANNAKAKIS, M. 1993. Primal-dual approximation algorithms for integral flow in multicut in trees, with application to matching and set cover. In Proceedings of the 20th International Colloquium on Automata, Languages and Programming.]]
20. GOEMANS,M.X.,GOLDBERG,A.V.,PLOTKIN, S., SHMOYS, D., TARDOS,E ., AND WILLIAMSON,D.P. 1994. Improved approximation algorithms for network design problems. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (Arlington, Va., Jan. 23-25). ACM, New York, pp. 223-232.]]
21. GOEMANS,M.X.,AND WILLIAMSON, D. P. 1995. A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 296-317.]]
22. GOEMANS,M.X.,AND WILLIAMSON, D. P. 1997. The primal-dual method for approximation algorithms and its application to network design problems. In Approximation Algorithms for NP-hard Problems, D. Hochbaum, ed. PWS, pp. 144-191.]]
23. GUHA, S., AND KHULLER, S. 1998. Greedy strikes back: Improved facility location algorithms. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, Calif., Jan.). ACM, New York, pp. 649-657.]]
24. HOCHBAUM, D. S. 1982. Heuristics for the fixed cost median problem. Math. Prog. 22, 148-162.]]
25. JAIN, K., MA cNDOIU, I., VAZIRANI,V.V.,AND WILLIAMSON, D. P. 1999. A primal-dual schema based approximation algorithm for the element connectivity problem. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, Md., Jan. 17-19). ACM, New York, pp. 484-489.]]
26. JAIN, K., AND VAZIRANI, V. V. 2000. An approximation algorithm for the fault tolerant metric facility location problem. In Proceedings of the 3rd Annual APPROX Conference. Lecture Notes in Computer Science, vol. 1671. Springer-Verlag, New York.]]
27. KAUFMAN, L., VANDEN EEDE, M., AND HANSEN, P. 1977. A plant and warehouse location problem. Oper. Res. Quart. 28, 547-557.]]
28. KORUPOLU,M.R.,PLAXTON,C.G.,AND RAJARAMAN, R. 1998. Analysis of a local search heuristic for facility location problems. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, Calif., Jan.) ACM, New York, pp. 1-10.]]
29. KUEHN,A.A.,AND HAMBURGER, M. J. 1963. A heuristic program for locating warehouses. Manage. Sci. 9, 643-666.]]
30. LIN, J.-H., AND VITTER, J. S. 1992. Approximation algorithms for geometric median problems. Inf. Proc. Lett. 44, 245-249.]]
31. LIN, J.-H., AND VITTER, J. S. 1992. e-approximation with minimum packing constraint violation. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM, New York, pp. 771-782.]]
32. METTU,R.R.,AND PLAXTON, C. G. 2000. The online median problem. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 339-348.]]
33. NEMHAUSER,G.L.,AND WOLSEY, L. A. 1990. Integer and Combinatorial Optimization. Wiley, New York.]]
34. RAJAGOPALAN, S., AND VAZIRANI, V. V. 1999. On the bidirected cut relaxation for the metric Steiner tree problem. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, Md., Jan. 17-19). ACM, New York, pp. 742-751.]]
35. SHMOYS,D.B.,TARDOS,E ' ., AND AARDAL, K. 1997. Approximation algorithms for facility location problems. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, Tex., May 4-6). ACM, New York, pp. 265-274.]]
36. STOLLSTEIMER, J. F. 1961. The effect of technical change and output expansion on the optimum number, size and location of pear marketing facilities in a California pear producing region. Ph.D. thesis, Univ. California at Berkeley, Berkeley, Calif.]]
37. STOLLSTEIMER, J. F. 1963. A working model for plant numbers and locations. J. Farm Econom. 45, 631-645.]]
38. VAZIRANI, V. V. 1995. Primal-dual schema based approximation algorithms. In Proceedings of the 1st Annual International Conference, COCOON. 650-652.]]
39. WILLIAMSON,D.P.,GOEMANS,M.X.,MIHAIL, M., AND VAZIRANI, V. V. 1995. A primal-dual approximation algorithm for generalized Steiner network problems. Combinatorica 15 (Dec.), 435-454.]]

Index Terms

• Theory of computation

  • Design and analysis of algorithms