Document Open Access Logo

Constant Approximation for Capacitated k-Median with (1+epsilon)-Capacity Violation

Authors Gökalp Demirci, Shi Li

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.73.pdf
  • Filesize: 0.64 MB
  • 14 pages

Document Identifiers

Author Details

Gökalp Demirci
Shi Li

Cite As Get BibTex

Gökalp Demirci and Shi Li. Constant Approximation for Capacitated k-Median with (1+epsilon)-Capacity Violation. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.73

Abstract

We study the Capacitated k-Median problem for which existing constant-factor approximation algorithms are all pseudo-approximations that violate either the capacities or the upper bound k on the number of open facilities. Using the natural LP relaxation for the problem, one can only hope to get the violation factor down to 2. Li [SODA'16] introduced a novel LP to go beyond the limit of 2 and gave a constant-factor approximation algorithm that opens (1 + epsilon)*k facilities.

We use the configuration LP of Li [SODA'16] to give a constant-factor approximation for the Capacitated k-Median problem in a seemingly harder configuration: we violate only the capacities by 1 + epsilon. This result settles the problem as far as pseudo-approximation algorithms are concerned.

Subject Classification

Keywords
  • Approximation Algorithms
  • Capacitated k-Median
  • Pseudo Approximation
  • Capacity Violation

Metrics

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

References

  1. Karen Aardal, Pieter L. van den Berg, Dion Gijswijt, and Shanfei Li. Approximation algorithms for hard capacitated k-facility location problems. European Journal of Operational Research, 242(2):358-368, 2015. URL: http://dx.doi.org/10.1016/j.ejor.2014.10.011.
  2. Hyung-Chan An, Mohit Singh, and Ola Svensson. LP-based algorithms for capacitated facility location. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014, 2014. Google Scholar
  3. V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit. Local search heuristic for k-median and facility location problems. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, STOC'01, pages 21-29, New York, NY, USA, 2001. ACM. URL: http://dx.doi.org/10.1145/380752.380755.
  4. Jarosław Byrka, Krzysztof Fleszar, Bartosz Rybicki, and Joachim Spoerhase. Bi-factor approximation algorithms for hard capacitated k-median problems. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), 2015. Google Scholar
  5. Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median, and positive correlation in budgeted optimization. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), 2015. Google Scholar
  6. Jarosław Byrka, Bartosz Rybicki, and Sumedha Uniyal. An approximation algorithm for uniform capacitated k-median problem with 1+ε capacity violation, 2015. arXiv:1511.07494. URL: http://arxiv.org/abs/arXiv:1511.07494.
  7. Robert D. Carr, Lisa K. Fleischer, Vitus J. Leung, and Cynthia A. Phillips. Strengthening integrality gaps for capacitated network design and covering problems. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'00, pages 106-115, Philadelphia, PA, USA, 2000. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=338219.338241.
  8. M. Charikar and S. Guha. Improved combinatorial algorithms for the facility location and k-median problems. In In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pages 378-388, 1999. Google Scholar
  9. M. Charikar, S. Guha, É. Tardos, and D. B. Shmoys. A constant-factor approximation algorithm for the k-median problem (extended abstract). In Proceedings of the thirty-first annual ACM symposium on Theory of computing, STOC'99, pages 1-10, New York, NY, USA, 1999. ACM. URL: http://dx.doi.org/10.1145/301250.301257.
  10. Julia Chuzhoy and Yuval Rabani. Approximating k-median with non-uniform capacities. In SODA ’05, pages 952-958, 2005. Google Scholar
  11. Sudipto Guha. Approximation Algorithms for Facility Location Problems. PhD thesis, Stanford University, Stanford, CA, USA, 2000. Google Scholar
  12. K. Jain, M. Mahdian, and A. Saberi. A new greedy approach for facility location problems. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, STOC'02, pages 731-740, New York, NY, USA, 2002. ACM. URL: http://dx.doi.org/10.1145/509907.510012.
  13. K Jain and V. 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. URL: http://dx.doi.org/10.1145/375827.375845.
  14. Shanfei Li. An improved approximation algorithm for the hard uniform capacitated k-median problem. In APPROX'14/RANDOM'14: Proceedings of the 17th International Workshop on Combinatorial Optimization Problems and the 18th International Workshop on Randomization and Computation, APPROX'14/RANDOM'14, 2014. Google Scholar
  15. Shi Li. On uniform capacitated k-median beyond the natural LP relaxation. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), 2015. Google Scholar
  16. Shi Li. Approximating capacitated k-median with (1 + ε)k open facilities. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pages 786-796, 2016. Google Scholar
  17. Shi Li and Ola Svensson. Approximating k-median via pseudo-approximation. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC'13, pages 901-910, New York, NY, USA, 2013. ACM. URL: http://dx.doi.org/10.1145/2488608.2488723.
  18. J. Lin and J. S. Vitter. ε-approximations with minimum packing constraint violation (extended abstract). In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC), Victoria, British Columbia, Canada, pages 771-782, 1992. Google Scholar
  19. D. B. Shmoys, É. Tardos, and K. Aardal. Approximation algorithms for facility location problems (extended abstract). In STOC'97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 265-274, New York, NY, USA, 1997. ACM. URL: http://dx.doi.org/10.1145/258533.258600.
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact