Document Open Access Logo

Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions

Authors Rajiv Raman, Saurabh Ray

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.78.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Author Details

Rajiv Raman
  • IIIT Delhi, India
Saurabh Ray
  • NYU Abu Dhabi, United Arab Emirates

Acknowledgements

The authors are grateful to Nabil H. Mustafa for ideas and comments.

Cite AsGet BibTex

Rajiv Raman and Saurabh Ray. Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 78:1-78:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.78

Abstract

In the Set Multicover problem, we are given a set system (X,𝒮), where X is a finite ground set, and 𝒮 is a collection of subsets of X. Each element x ∈ X has a non-negative demand d(x). The goal is to pick a smallest cardinality sub-collection 𝒮' of 𝒮 such that each point is covered by at least d(x) sets from 𝒮'. In this paper, we study the set multicover problem for set systems defined by points and non-piercing regions in the plane, which includes disks, pseudodisks, k-admissible regions, squares, unit height rectangles, homothets of convex sets, upward paths on a tree, etc. We give a polynomial time (2+ε)-approximation algorithm for the set multicover problem (P, ℛ), where P is a set of points with demands, and ℛ is a set of non-piercing regions, as well as for the set multicover problem (𝒟, P), where 𝒟 is a set of pseudodisks with demands, and P is a set of points in the plane, which is the hitting set problem with demands.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
  • Theory of computation → Computational geometry
Keywords
  • Approximation algorithms
  • geometry
  • Covering

Metrics

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

References

  1. Pankaj K. Agarwal and Jiangwei Pan. Near-linear algorithms for geometric hitting sets and set covers. Discret. Comput. Geom., 63(2):460-482, 2020. URL: https://doi.org/10.1007/s00454-019-00099-6.
  2. 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
  3. Nikhil Bansal and Kirk Pruhs. Weighted geometric set multi-cover via quasi-uniform sampling. JoCG, 7(1):221-236, 2016. Google Scholar
  4. Aniket Basu Roy, Sathish Govindarajan, Rajiv Raman, and Saurabh Ray. Packing and covering with non-piercing regions. Discrete & Computational Geometry, 2018. Google Scholar
  5. 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
  6. Norbert Bus, Shashwat Garg, Nabil H. Mustafa, and Saurabh Ray. Tighter estimates for ε-nets for disks. Comput. Geom., 53:27-35, 2016. URL: https://doi.org/10.1016/j.comgeo.2015.12.002.
  7. 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
  8. Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. Discrete & Computational Geometry, 48(2):373-392, 2012. Google Scholar
  9. 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.
  10. Timothy M. Chan and Qizheng He. Faster approximation algorithms for geometric set cover. CoRR, abs/2003.13420, 2020. URL: http://arxiv.org/abs/2003.13420.
  11. 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.
  12. Chandra Chekuri, Sariel Har-Peled, and Kent Quanrud. Fast lp-based approximations for geometric packing and covering problems. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1019-1038. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.62.
  13. Kenneth L. Clarkson and Kasturi R. Varadarajan. Improved approximation algorithms for geometric set cover. Discrete & Computational Geometry, 37(1):43-58, 2007. URL: https://doi.org/10.1007/s00454-006-1273-8.
  14. Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu. Local search yields approximation schemes for k-means and k-median in euclidean and minor-free metrics. SIAM J. Comput., 48(2):644-667, 2019. URL: https://doi.org/10.1137/17M112717X.
  15. Vincent Cohen-Addad and Claire Mathieu. Effectiveness of local search for geometric optimization. In Proceedings of the Thirty-first International Symposium on Computational Geometry, SoCG '15, pages 329-343, Dagstuhl, Germany, 2015. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  16. Thomas Erlebach and Erik Jan van Leeuwen. PTAS for weighted set cover on unit squares. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, pages 166-177, 2010. Google Scholar
  17. Guy Even, Dror Rawitz, and Shimon Shahar. Hitting sets when the vc-dimension is small. Inf. Process. Lett., 95(2):358-362, 2005. URL: https://doi.org/10.1016/j.ipl.2005.03.010.
  18. Uriel Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634-652, 1998. URL: https://doi.org/10.1145/285055.285059.
  19. Zachary Friggstad, Kamyar Khodamoradi, Mohsen Rezapour, and Mohammad R. Salavatipour. Approximation schemes for clustering with outliers. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 398-414, 2018. Google Scholar
  20. Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour. Local search yields a PTAS for k-means in doubling metrics. SIAM J. Comput., 48(2):452-480, 2019. URL: https://doi.org/10.1137/17M1127181.
  21. 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
  22. David Haussler and Emo Welzl. epsilon-nets and simplex range queries. Discrete & Computational Geometry, 2:127-151, 1987. URL: https://doi.org/10.1007/BF02187876.
  23. Bruno Jartoux and Nabil H. Mustafa. Optimality of Geometric Local Search. In 34th International Symposium on Computational Geometry (SoCG 2018), Leibniz International Proceedings in Informatics (LIPIcs), pages 48:1-48:15, 2018. Google Scholar
  24. János Komlós, János Pach, and Gerhard J. Woeginger. Almost tight bounds for epsilon-nets. Discret. Comput. Geom., 7:163-173, 1992. URL: https://doi.org/10.1007/BF02187833.
  25. Erik Krohn, Matt Gibson, Gaurav Kanade, and Kasturi Varadarajan. Guarding terrains via local search. Journal of Computational Geometry, 5(1):168-178, 2014. Google Scholar
  26. Jian Li and Yifei Jin. A PTAS for the weighted unit disk cover problem. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 898-909, 2015. Google Scholar
  27. Richard J. Lipton and Robert E. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177-189, 1979. Google Scholar
  28. Nabil H. Mustafa and Saurabh Ray. Improved results on geometric hitting set problems. Discrete & Computational Geometry, 44(4):883-895, 2010. Google Scholar
  29. Rom Pinchasi. A finite family of pseudodiscs must include a "small" pseudodisc. SIAM J. Discret. Math., 28(4):1930-1934, 2014. URL: https://doi.org/10.1137/130949750.
  30. 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
  31. 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
  32. Vijay V. Vazirani. Approximation algorithms. Springer, 2001. URL: http://www.springer.com/computer/theoretical+computer+science/book/978-3-540-65367-7.
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