Abstract
We consider the facility location problem where each facility can serve at most U clients. We analyze a local search algorithm for this problem which uses only the operations of add, delete and swap and prove that any locally optimum solution is no more than 3 times the global optimum. This improves on a result of Chudak and Williamson who proved an approximation ratio of \({3+2\sqrt{2}}\) for the same algorithm. We also provide an example which shows that any local search algorithm which uses only these three operations cannot achieve an approximation guarantee better than 3.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Arya V., Garg N., Khandekar R., Meyerson A., Munagala K., Pandit V.: Local search heuristics for k-median and facility location problems. SIAM J. Comput. 33(3), 544–562 (2004)
Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pp. 378–388 (1999)
Chudak F., Williamson D.P.: Improved approximation algorithms for capacitated facility location problems. Math. Program. 102(2), 207–222 (2005)
Korupolu M.R., Plaxton C.G., Rajaraman R.: Analysis of a local search heuristic for facility location problems. J. Algorithms 37(1), 146–188 (2000)
Mahdian, M., Pál, M.: Universal facility location. In: Proceedings of the 11th Annual European Symposium on Algorithms, volume 2832 of Lecture Notes in Computer Science, pp. 409–421 (2003)
Mahdian, M., Ye, Y., Zhang, J.: A 2-approximation algorithm for the soft-capacitated facility location problem. In: Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization, volume 2764 of Lecture Notes in Computer Science, pp. 129–140 (2003)
Pál, M., Tardos, É., Wexler, T.: Facility location with nonuniform hard capacities. In: FOCS ’01: Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p. 329. IEEE Computer Society, Washington, DC, USA (2001)
Zhang J., Chen B., Ye Y.: A multiexchange local search algorithm for the capacitated facility location problem. Math. Oper. Res. 30(2), 389–403 (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
Work done as part of the “Approximation Algorithms” partner group of MPI-Informatik, Germany.
Rights and permissions
About this article
Cite this article
Aggarwal, A., Louis, A., Bansal, M. et al. A 3-approximation algorithm for the facility location problem with uniform capacities. Math. Program. 141, 527–547 (2013). https://doi.org/10.1007/s10107-012-0565-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-012-0565-4