Document Open Access Logo

An Improved Approximation Algorithm for the Hard Uniform Capacitated k-median Problem

Author Shanfei Li

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2014.325.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • Approximation algorithm; k-median problem; LP-rounding; Hard capacities

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

In the k-median problem, given a set of locations, the goal is to select a subset of at most k centers so as to minimize the total cost of connecting each location to its nearest center. We study the uniform hard capacitated version of the k-median problem, in which each selected center can only serve a limited number of locations.

Inspired by the algorithm of Charikar, Guha, Tardos and Shmoys,
we give an improved approximation algorithm for this problem with increasing the capacities by a constant factor, which improves the previous best approximation algorithm proposed by Byrka, Fleszar, Rybicki and Spoerhase.

Cite As Get BibTex

Shanfei Li. An Improved Approximation Algorithm for the Hard Uniform Capacitated k-median Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 325-338, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.325

Author Details

Shanfei Li

References

  1. Aaron Archer, Ranjithkumar Rajagopalan, and David B. Shmoys. Lagrangian relaxation for the k-median problem: New insights and continuity properties. In Giuseppe Di Battista and Uri Zwick, editors, ESA, volume 2832 of LNCS, pages 31-42. Springer, 2003. Google Scholar
  2. Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristic for k-median and facility location problems. In Jeffrey Scott Vitter, Paul G. Spirakis, and Mihalis Yannakakis, editors, STOC, pages 21-29. ACM, 2001. Google Scholar
  3. Yair Bartal, Moses Charikar, and Danny Raz. Approximating min-sum k-clustering in metric spaces. In Jeffrey Scott Vitter, Paul G. Spirakis, and Mihalis Yannakakis, editors, STOC, pages 11-20. ACM, 2001. Google Scholar
  4. Paul S. Bradley, Usama M. Fayyad, and Olvi L. Mangasarian. Mathematical programming for data mining: Formulations and challenges. INFORMS Journal on Computing, 11(3):217-238, 1999. Google Scholar
  5. Jaroslaw Byrka, Krzysztof Fleszar, Bartosz Rybicki, and Joachim Spoerhase. A constant-factor approximation algorithm for uniform hard capacitated k-median. CoRR, abs/1312.6550, 2013. Google Scholar
  6. Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median, and positive correlation in budgeted optimization. CoRR, abs/1406.2951, 2014. Google Scholar
  7. Moses Charikar. Algorithms for clustering problems. PhD thesis, Standford University, 2000. Google Scholar
  8. Moses Charikar and Sudipto Guha. Improved combinatorial algorithms for the facility location and k-median problems. In FOCS, pages 378-388. IEEE Computer Society, 1999. Google Scholar
  9. Moses Charikar, Sudipto Guha, Éva Tardos, and David B. Shmoys. A constant-factor approximation algorithm for the k-median problem (extended abstract). In Jeffrey Scott Vitter, Lawrence L. Larmore, and Frank Thomson Leighton, editors, STOC, pages 1-10. ACM, 1999. Google Scholar
  10. Julia Chuzhoy and Yuval Rabani. Approximating k-median with non-uniform capacities. In SODA, pages 952-958. SIAM, 2005. Google Scholar
  11. Dion Gijswijt and Shanfei Li. Approximation algorithms for the capacitated k-facility location problems. CoRR, abs/1311.4759, 2013. Google Scholar
  12. Sudipto Guha. Approximation algorithm for faciity location problems. PhD thesis, Standford University, 2000. Google Scholar
  13. Anil K. Jain and Richard C. Dubes. Algorithms for clustering data. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1988. Google Scholar
  14. Kamal Jain, Mohammad Mahdian, and Amin Saberi. A new greedy approach for facility location problems. In John H. Reif, editor, STOC, pages 731-740. ACM, 2002. Google Scholar
  15. Kamal Jain and Vijay V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. J. ACM, 48(2):274-296, 2001. Google Scholar
  16. Madhukar R. Korupolu, C. Greg Plaxton, and Rajmohan Rajaraman. Analysis of a local search heuristic for facility location problems. J. Algorithms, 37(1):146-188, 2000. Google Scholar
  17. Shi Li and Ola Svensson. Approximating k-median via pseudo-approximation. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, STOC, pages 901-910. ACM, 2013. Google Scholar
  18. Jyh-Han Lin and Jeffrey Scott Vitter. epsilon-approximations with minimum packing constraint violation (extended abstract). In S. Rao Kosaraju, Mike Fellows, Avi Wigderson, and John A. Ellis, editors, STOC, pages 771-782. ACM, 1992. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact