Document Open Access Logo

On Geometric Priority Set Cover Problems

Authors Aritra Banik, Rajiv Raman, Saurabh Ray

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.12.pdf
  • Filesize: 0.69 MB
  • 14 pages

Document Identifiers

Author Details

Aritra Banik
  • National Institute of Science Education and Research, HBNI, Bhubaneswar, India
Rajiv Raman
  • Université Clermont Auvergne, Clermont Auvergne INP, CNRS, Mines Saint-Etienne, LIMOS, F-63000, Clermont-Ferrand, France
Saurabh Ray
  • New York University, Abu Dhabi, UAE

Funding

  • Raman, Rajiv: This work has been partially supported by the French government research program "Investissements d’Avenir" through the IDEX-ISITE initiative 16-IDEX-0001 (CAP 20– 25).

Cite AsGet BibTex

Aritra Banik, Rajiv Raman, and Saurabh Ray. On Geometric Priority Set Cover Problems. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ISAAC.2021.12

Abstract

We study the priority set cover problem for simple geometric set systems in the plane. For pseudo-halfspaces in the plane we obtain a PTAS via local search by showing that the corresponding set system admits a planar support. We show that the problem is APX-hard even for unit disks in the plane and argue that in this case the standard local search algorithm can output a solution that is arbitrarily bad compared to the optimal solution. We then present an LP-relative constant factor approximation algorithm (which also works in the weighted setting) for unit disks via quasi-uniform sampling. As a consequence we obtain a constant factor approximation for the capacitated set cover problem with unit disks. For arbitrary size disks, we show that the problem is at least as hard as the vertex cover problem in general graphs even when the disks have nearly equal sizes. We also present a few simple results for unit squares and orthants in the plane.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
  • Theory of computation → Computational geometry
Keywords
  • Approximation algorithms
  • geometric set cover
  • local search
  • quasi-uniform sampling

Metrics

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

References

  1. Anna Adamaszek and Andreas Wiese. Approximation schemes for maximum weight independent set of rectangles. In Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS '13, pages 400-409, Washington, DC, USA, 2013. IEEE Computer Society. Google Scholar
  2. Anna Adamaszek and Andreas Wiese. A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '14, pages 645-656, 2014. Google Scholar
  3. Pankaj K. Agarwal, Ravid Cohen, Dan Halperin, and Wolfgang Mulzer. Dynamic maintenance of the lower envelope of pseudo-lines. CoRR, abs/1902.09565, 2019. URL: http://arxiv.org/abs/1902.09565.
  4. Pankaj K. Agarwal and Micha Sharir. Pseudo-line arrangements: Duality, algorithms, and applications. SIAM J. Comput., 34(3):526-552, 2005. URL: https://doi.org/10.1137/S0097539703433900.
  5. Rom Aschner, Matthew J. Katz, Gila Morgenstern, and Yelena Yuditsky. Approximation schemes for covering and packing. In WALCOM: Algorithms and Computation, volume 7748 of Lecture Notes in Computer Science, pages 89-100. Springer Berlin Heidelberg, 2013. Google Scholar
  6. Nikhil Bansal and Kirk Pruhs. Weighted geometric set multi-cover via quasi-uniform sampling. JoCG, 7(1):221-236, 2016. Google Scholar
  7. Aniket Basu Roy, Sathish Govindarajan, Rajiv Raman, and Saurabh Ray. Packing and covering with non-piercing regions. Discrete & Computational Geometry, 2018. Google Scholar
  8. Karl Bringmann, Sándor Kisfaludi-Bak, Michal Pilipczuk, and Erik Jan van Leeuwen. On geometric set cover for orthants. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 26:1-26:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.26.
  9. Hervé Brönnimann and Michael T. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete & Computational Geometry, 14(1):463-479, 1995. Google Scholar
  10. Robert D. Carr, Lisa Fleischer, Vitus J. Leung, and Cynthia A. Phillips. Strengthening integrality gaps for capacitated network design and covering problems. In David B. Shmoys, editor, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 9-11, 2000, San Francisco, CA, USA, pages 106-115. ACM/SIAM, 2000. URL: http://dl.acm.org/citation.cfm?id=338219.338241.
  11. Deeparnab Chakrabarty, Elyot Grant, and Jochen Könemann. On column-restricted and priority covering integer programs. In Friedrich Eisenbrand and F. Bruce Shepherd, editors, Integer Programming and Combinatorial Optimization, 14th International Conference, IPCO 2010, Lausanne, Switzerland, June 9-11, 2010. Proceedings, volume 6080 of Lecture Notes in Computer Science, pages 355-368. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-13036-6_27.
  12. Timothy M. Chan and Elyot Grant. Exact algorithms and apx-hardness results for geometric packing and covering problems. Comput. Geom. Theory Appl., 47(2), February 2014. Google Scholar
  13. 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 '12, pages 1576-1585, 2012. Google Scholar
  14. Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. Discrete & Computational Geometry, 48(2):373-392, 2012. URL: https://doi.org/10.1007/s00454-012-9417-5.
  15. Chandra Chekuri, Kenneth L. Clarkson, and Sariel Har-Peled. On the set multicover problem in geometric settings. ACM Trans. Algorithms, 9(1):9:1-9:17, 2012. URL: https://doi.org/10.1145/2390176.2390185.
  16. Kenneth L Clarkson and Peter W Shor. Applications of random sampling in computational geometry, ii. Discrete & Computational Geometry, 4(5):387-421, 1989. Google Scholar
  17. Gautam K. Das, Robert Fraser, Alejandro López-Ortiz, and Bradford G. Nickerson. On the discrete unit disk cover problem. In Naoki Katoh and Amit Kumar, editors, WALCOM: Algorithms and Computation - 5th International Workshop, WALCOM 2011, New Delhi, India, February 18-20, 2011. Proceedings, volume 6552 of Lecture Notes in Computer Science, pages 146-157. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-19094-0_16.
  18. Irit Dinur and Samuel Safra. On the hardness of approximating minimum vertex cover. Annals of mathematics, pages 439-485, 2005. Google Scholar
  19. Matt Gibson and Imran A. Pirwani. Algorithms for dominating set in disk graphs: Breaking the log n barrier. In Algorithms - ESA 2010 - 18th Annual European Symposium, Liverpool, United Kingdom, September 6-8, 2010, Proceedings, pages 243-254, 2010. Google Scholar
  20. B. Grünbaum and Conference Board of the Mathematical Sciences. Arrangements and Spreads. Regional conference series in mathematics. Conference Board of the Mathematical Sciences, 1972. URL: https://books.google.co.in/books?id=M2NjAQAACAAJ.
  21. Sariel Har-Peled and Mira Lee. Weighted geometric set cover problems revisited. J. Comput. Geom., 3(1):65-85, 2012. URL: https://doi.org/10.20382/jocg.v3i1a4.
  22. Dorit S. Hochbaum and Wolfgang Maass. Fast approximation algorithms for a nonconvex covering problem. Journal of algorithms, 8(3):305-323, 1987. Google Scholar
  23. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci., 74(3):335-349, 2008. URL: https://doi.org/10.1016/j.jcss.2007.06.019.
  24. Nabil H. Mustafa, Rajiv Raman, and Saurabh Ray. Quasi-polynomial time approximation scheme for weighted geometric set cover on pseudodisks and halfspaces. SIAM Journal on Computing, 44(6):1650-1669, 2015. Google Scholar
  25. Nabil H. Mustafa and Saurabh Ray. Improved results on geometric hitting set problems. Discrete & Computational Geometry, 44(4):883-895, 2010. Google Scholar
  26. Rajiv Raman and Saurabh Ray. Planar support for non-piercing regions and applications. In 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, pages 69:1-69:14, 2018. Google Scholar
  27. Rajiv Raman and Saurabh Ray. Improved approximation algorithm for set multicover with non-piercing regions. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 78:1-78:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.78.
  28. Kasturi Varadarajan. Weighted geometric set cover via quasi-uniform sampling. In Proceedings of the 42nd ACM Symposium on Theory of Computing, pages 641-648, 2010. 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact