Capacitated Covering Problems in Geometric Spaces

Authors Sayan Bandyapadhyay, Santanu Bhowmick, Tanmay Inamdar, Kasturi Varadarajan



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.7.pdf
  • Filesize: 383 kB
  • 15 pages

Document Identifiers

Author Details

Sayan Bandyapadhyay
Santanu Bhowmick
Tanmay Inamdar
Kasturi Varadarajan

Cite AsGet BibTex

Sayan Bandyapadhyay, Santanu Bhowmick, Tanmay Inamdar, and Kasturi Varadarajan. Capacitated Covering Problems in Geometric Spaces. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SoCG.2018.7

Abstract

In this article, we consider the following capacitated covering problem. We are given a set P of n points and a set B of balls from some metric space, and a positive integer U that represents the capacity of each of the balls in B. We would like to compute a subset B' subseteq B of balls and assign each point in P to some ball in B' that contains it, such that the number of points assigned to any ball is at most U. The objective function that we would like to minimize is the cardinality of B'. We consider this problem in arbitrary metric spaces as well as Euclidean spaces of constant dimension. In the metric setting, even the uncapacitated version of the problem is hard to approximate to within a logarithmic factor. In the Euclidean setting, the best known approximation guarantee in dimensions 3 and higher is logarithmic in the number of points. Thus we focus on obtaining "bi-criteria" approximations. In particular, we are allowed to expand the balls in our solution by some factor, but optimal solutions do not have that flexibility. Our main result is that allowing constant factor expansion of the input balls suffices to obtain constant approximations for this problem. In fact, in the Euclidean setting, only (1+epsilon) factor expansion is sufficient for any epsilon > 0, with the approximation factor being a polynomial in 1/epsilon. We obtain these results using a unified scheme for rounding the natural LP relaxation; this scheme may be useful for other capacitated covering problems. We also complement these bi-criteria approximations by obtaining hardness of approximation results that shed light on our understanding of these problems.
Keywords
  • Capacitated covering
  • Geometric set cover
  • LP rounding
  • Bi-criteria approximation

Metrics

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

References

  1. Anshul Aggarwal, Venkatesan T. Chakaravarthy, Neelima Gupta, Yogish Sabharwal, Sachin Sharma, and Sonika Thakral. Replica placement on bounded treewidth graphs. In Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 - August 2, 2017, Proceedings, pages 13-24, 2017. URL: http://dx.doi.org/10.1007/978-3-319-62127-2_2.
  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: http://dx.doi.org/10.1007/s10107-014-0857-y.
  3. Hyung-Chan An, Mohit Singh, and Ola Svensson. Lp-based algorithms for capacitated facility location. In FOCS, pages 256-265, 2014. Google Scholar
  4. Boris Aronov, Esther Ezra, and Micha Sharir. Small-size ε-nets for axis-parallel rectangles and boxes. SIAM J. Comput., 39(7):3248-3282, 2010. URL: http://dx.doi.org/10.1137/090762968.
  5. Judit Bar-Ilan, Guy Kortsarz, and David Peleg. How to allocate network centers. J. Algorithms, 15(3):385-415, 1993. URL: http://dblp.uni-trier.de/db/journals/jal/jal15.html#Bar-IlanKP93.
  6. Amariah Becker. Capacitated dominating set on planar graphs. In Approximation and Online Algorithms - 15th International Workshop, WAOA 2017, Vienna, Austria, September 7-8, 2017. Google Scholar
  7. Piotr Berman, Marek Karpinski, and Andrzej Lingas. Exact and approximation algorithms for geometric and capacitated set cover problems. Algorithmica, 64(2):295-310, 2012. Google Scholar
  8. Prosenjit Bose, Paz Carmi, Mirela Damian, Robin Y. Flatland, Matthew J. Katz, and Anil Maheshwari. Switching to directional antennas with constant increase in radius and hop distance. Algorithmica, 69(2):397-409, 2014. Google Scholar
  9. Hervé Brönnimann and Michael T. Goodrich. Almost optimal set covers in finite vc-dimension. Discrete & Computational Geometry, 14(4):463-479, 1995. URL: http://dx.doi.org/10.1007/BF02570718.
  10. Timothy M. Chan, Elyot Grant, Jochen Könemann, and Malcolm Sharpe. Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1576-1585, 2012. URL: https://dl.acm.org/citation.cfm?id=2095241.
  11. Julia Chuzhoy and Joseph Naor. Covering problems with hard capacities. SIAM J. Comput., 36(2):498-515, 2006. Google Scholar
  12. Kenneth L. Clarkson and Kasturi R. Varadarajan. Improved approximation algorithms for geometric set cover. Discrete & Computational Geometry, 37(1):43-58, 2007. Google Scholar
  13. 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
  14. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 624-633, 2014. URL: http://dx.doi.org/10.1145/2591796.2591884.
  15. 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
  16. Taha Ghasemi and Mohammadreza Razzazi. A PTAS for the cardinality constrained covering with unit balls. Theor. Comput. Sci., 527:50-60, 2014. Google Scholar
  17. Sathish Govindarajan, Rajiv Raman, Saurabh Ray, and Aniket Basu Roy. Packing and covering with non-piercing regions. In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, pages 47:1-47:17, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.47.
  18. Sariel Har-Peled and Mira Lee. Weighted geometric set cover problems revisited. JoCG, 3(1):65-85, 2012. Google Scholar
  19. Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM, 32(1):130-136, 1985. 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. Nissan Lev-Tov and David Peleg. Polynomial time approximation schemes for base station coverage with minimum total radii. Computer Networks, 47(4):489-501, 2005. Google Scholar
  23. Retsef Levi, David B. Shmoys, and Chaitanya Swamy. Lp-based approximation algorithms for capacitated facility location. Math. Program., 131(1-2):365-379, 2012. URL: http://dx.doi.org/10.1007/s10107-010-0380-8.
  24. Shi Li. On uniform capacitated k-median beyond the natural LP relaxation. In SODA, pages 696-707, 2015. 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: http://dx.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. URL: http://dx.doi.org/10.1007/s00454-010-9285-9.
  27. Kasturi R. Varadarajan. Weighted geometric set cover via quasi-uniform sampling. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 641-648, 2010. URL: http://dx.doi.org/10.1145/1806689.1806777.
  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