Document Open Access Logo

Improved Bounds for Metric Capacitated Covering Problems

Author Sayan Bandyapadhyay

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2020.9.pdf
  • Filesize: 449 kB
  • 17 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Approximation algorithms
Keywords
  • Capacitated covering
  • approximation algorithms
  • bicriteria approximation
  • LP rounding

Metrics

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

Abstract

In the Metric Capacitated Covering (MCC) problem, given a set of balls ℬ in a metric space P with metric d and a capacity parameter U, the goal is to find a minimum sized subset ℬ' ⊆ ℬ and an assignment of the points in P to the balls in ℬ' such that each point is assigned to a ball that contains it and each ball is assigned with at most U points. MCC achieves an O(log |P|)-approximation using a greedy algorithm. On the other hand, it is hard to approximate within a factor of o(log |P|) even with β < 3 factor expansion of the balls. Bandyapadhyay et al. [SoCG 2018, DCG 2019] showed that one can obtain an O(1)-approximation for the problem with 6.47 factor expansion of the balls. An open question left by their work is to reduce the gap between the lower bound 3 and the upper bound 6.47. In this current work, we show that it is possible to obtain an O(1)-approximation with only 4.24 factor expansion of the balls. We also show a similar upper bound of 5 for a more generalized version of MCC for which the best previously known bound was 9.

Cite As Get BibTex

Sayan Bandyapadhyay. Improved Bounds for Metric Capacitated Covering Problems. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.9

Author Details

Sayan Bandyapadhyay
  • Department of Informatics, University of Bergen, Norway

Funding

This work is partly supported by the Research Council of Norway via the project "MULTIVAL".

Acknowledgements

I am indebted to Tanmay Inamdar for giving invaluable feedback on this work. I also thank the anonymous reviewers whose suggestions have helped to further improve the quality of the paper.

References

  1. Ankit Aggarwal, Anand Louis, Manisha Bansal, Naveen Garg, Neelima Gupta, Shubham Gupta, and Surabhi Jain. A 3-approximation algorithm for the facility location problem with uniform capacities. Math. Program., 141(1-2):527-547, 2013. Google Scholar
  2. Hyung-Chan An, Aditya Bhaskara, Chandra Chekuri, Shalmoli Gupta, Vivek Madan, and Ola Svensson. Centrality of trees for capacitated k-center. Math. Program., 154(1-2):29-53, 2015. URL: https://doi.org/10.1007/s10107-014-0857-y.
  3. Hyung-Chan An, Mohit Singh, and Ola Svensson. Lp-based algorithms for capacitated facility location. SIAM J. Comput., 46(1):272-306, 2017. Google Scholar
  4. Sayan Bandyapadhyay, Santanu Bhowmick, Tanmay Inamdar, and Kasturi Varadarajan. Capacitated covering problems in geometric spaces. Discrete & Computational Geometry, pages 1-31, 2019. Google Scholar
  5. Manisha Bansal, Naveen Garg, and Neelima Gupta. A 5-approximation for capacitated facility location. In Leah Epstein and Paolo Ferragina, editors, Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings, volume 7501 of Lecture Notes in Computer Science, pages 133-144. Springer, 2012. Google Scholar
  6. Judit Bar-Ilan, Guy Kortsarz, and David Peleg. How to allocate network centers. J. Algorithms, 15(3):385-415, 1993. URL: https://doi.org/10.1006/jagm.1993.1047.
  7. Hervé Brönnimann and Michael T. Goodrich. Almost optimal set covers in finite vc-dimension. Discrete & Computational Geometry, 14(4):463-479, 1995. Google Scholar
  8. Jaroslaw Byrka, Krzysztof Fleszar, Bartosz Rybicki, and Joachim Spoerhase. Bi-factor approximation algorithms for hard capacitated k-median problems. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 722-736. SIAM, 2015. Google Scholar
  9. Jaroslaw Byrka, Bartosz Rybicki, and Sumedha Uniyal. An approximation algorithm for uniform capacitated k-median problem with 1+backslashepsilon capacity violation. In Quentin Louveaux and Martin Skutella, editors, Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings, volume 9682 of Lecture Notes in Computer Science, pages 262-274. Springer, 2016. Google Scholar
  10. Moses Charikar, Sudipto Guha, Éva Tardos, and David B. Shmoys. A constant-factor approximation algorithm for the k-median problem. J. Comput. Syst. Sci., 65(1):129-149, 2002. Google Scholar
  11. Fabián A. Chudak and David P. Williamson. Improved approximation algorithms for capacitated facility location problems. Math. Program., 102(2):207-222, 2005. Google Scholar
  12. Julia Chuzhoy and Joseph Naor. Covering problems with hard capacities. SIAM J. Comput., 36(2):498-515, 2006. Google Scholar
  13. Julia Chuzhoy and Yuval Rabani. Approximating k-median with non-uniform capacities. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 952-958. SIAM, 2005. Google Scholar
  14. Marek Cygan, MohammadTaghi Hajiaghayi, and Samir Khuller. LP rounding for k-centers with non-uniform hard capacities. In FOCS, pages 273-282, 2012. Google Scholar
  15. H. 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, July 11-15, 2016, Rome, Italy, pages 73:1-73:14, 2016. Google Scholar
  16. Uriel Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634-652, 1998. Google Scholar
  17. Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, and Srinivasan Aravind. An improved approximation algorithm for vertex cover with hard capacities. J. Comput. Syst. Sci., 72(1):16-33, 2006. Google Scholar
  18. Taha Ghasemi and Mohammadreza Razzazi. A PTAS for the cardinality constrained covering with unit balls. Theor. Comput. Sci., 527:50-60, 2014. Google Scholar
  19. Sariel Har-Peled and Mira Lee. Weighted geometric set cover problems revisited. JoCG, 3(1):65-85, 2012. Google Scholar
  20. Mong-Jen Kao. Iterative partial rounding for vertex cover with hard capacities. In SODA, pages 2638-2653, 2017. Google Scholar
  21. Samir Khuller and Yoram J. Sussmann. The capacitated K-center problem. SIAM J. Discrete Math., 13(3):403-418, 2000. Google Scholar
  22. 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
  23. Shi Li. On uniform capacitated k-median beyond the natural LP relaxation. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 696-707, 2015. Google Scholar
  24. Shi Li. On uniform capacitated k-median beyond the natural LP relaxation. ACM Trans. Algorithms, 13(2):22:1-22:18, 2017. Google Scholar
  25. Robert Lupton, F. Miller Maley, and Neal E. Young. Data collection for the sloan digital sky survey - A network-flow heuristic. J. Algorithms, 27(2):339-356, 1998. URL: https://doi.org/10.1006/jagm.1997.0922.
  26. Nabil H. Mustafa and Saurabh Ray. Improved results on geometric hitting set problems. Discrete & Computational Geometry, 44(4):883-895, 2010. Google Scholar
  27. Martin Pál, Éva Tardos, and Tom Wexler. Facility location with nonuniform hard capacities. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 329-338. IEEE Computer Society, 2001. Google Scholar
  28. Laurence A. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385-393, 1982. Google Scholar
  29. Sam Chiu-wai Wong. Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs. In SODA, pages 2626-2637, 2017. 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