Document Open Access Logo

Faster Approximation Algorithms for Geometric Set Cover

Authors Timothy M. Chan , Qizheng He

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.27.pdf
  • Filesize: 481 kB
  • 14 pages

Document Identifiers

Author Details

Timothy M. Chan
  • Department of Computer Science, University of Illinois at Urbana-Champaign, IL, USA
Qizheng He
  • Department of Computer Science, University of Illinois at Urbana-Champaign, IL, USA

Funding

  • Chan, Timothy M.: Supported in part by NSF Grant CCF-1814026.

Cite As Get BibTex

Timothy M. Chan and Qizheng He. Faster Approximation Algorithms for Geometric Set Cover. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SoCG.2020.27

Abstract

We improve the running times of O(1)-approximation algorithms for the set cover problem in geometric settings, specifically, covering points by disks in the plane, or covering points by halfspaces in three dimensions. In the unweighted case, Agarwal and Pan [SoCG 2014] gave a randomized O(n log⁴n)-time, O(1)-approximation algorithm, by using variants of the multiplicative weight update (MWU) method combined with geometric data structures. We simplify the data structure requirement in one of their methods and obtain a deterministic O(n log³n log log n)-time algorithm. With further new ideas, we obtain a still faster randomized O(n log n(log log n)^O(1))-time algorithm.
For the weighted problem, we also give a randomized O(n log⁴n log log n)-time, O(1)-approximation algorithm, by simple modifications to the MWU method and the quasi-uniform sampling technique.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Set cover
  • approximation algorithms
  • multiplicate weight update method
  • random sampling
  • shallow cuttings

Metrics

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

Related Versions

References

  1. Peyman Afshani and Timothy M. Chan. On approximate range counting and depth. Discrete & Computational Geometry, 42(1):3-21, 2009. URL: https://doi.org/10.1007/s00454-009-9177-z.
  2. Peyman Afshani and Timothy M. Chan. Optimal halfspace range reporting in three dimensions. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 180-186, 2009. Google Scholar
  3. Peyman Afshani, Chris Hamilton, and Norbert Zeh. A general approach for cache-oblivious range reporting and approximate range counting. Computational Geometry, 43(8):700-712, 2010. Google Scholar
  4. Pankaj K. Agarwal and Jiangwei Pan. Near-linear algorithms for geometric hitting sets and set covers. In Proceedings of the 30th Symposium on Computational Geometry (SoCG), page 271, 2014. Google Scholar
  5. Boris Aronov, Esther Ezra, and Micha Sharir. Small-size ε-nets for axis-parallel rectangles and boxes. SIAM Journal on Computing, 39(7):3248-3282, 2010. URL: https://doi.org/10.1137/090762968.
  6. Jon Louis Bentley and James B. Saxe. Decomposable searching problems I. static-to-dynamic transformation. Journal of Algorithms, 1(4):301-358, 1980. Google Scholar
  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. Norbert Bus, Shashwat Garg, Nabil H. Mustafa, and Saurabh Ray. Limits of local search: Quality and efficiency. Discrete & Computational Geometry, 57(3):607-624, 2017. URL: https://doi.org/10.1007/s00454-016-9819-x.
  9. Norbert Bus, Nabil H. Mustafa, and Saurabh Ray. Practical and efficient algorithms for the geometric hitting set problem. Discrete Applied Mathematics, 240:25-32, 2018. Google Scholar
  10. Timothy M. Chan. Random sampling, halfspace range reporting, and construction of (≤ k)-levels in three dimensions. SIAM Journal on Computing, 30(2):561-575, 2000. URL: https://doi.org/10.1137/S0097539798349188.
  11. Timothy M. Chan. Polynomial-time approximation schemes for packing and piercing fat objects. Journal of Algorithms, 46(2):178-189, 2003. URL: https://doi.org/10.1016/S0196-6774(02)00294-8.
  12. Timothy M. Chan. Dynamic geometric data structures via shallow cuttings. In Proceedings of the 35th Symposium on Computational Geometry (SoCG), pages 24:1-24:13, 2019. 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 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1576-1585, 2012. Google Scholar
  14. Timothy M. Chan, Kasper Green Larsen, and Mihai Pătraşcu. Orthogonal range searching on the RAM, revisited. In Proceedings of the 27th Symposium on Computational Geometry (SoCG), pages 1-10, 2011. Google Scholar
  15. Timothy M. Chan and Konstantinos Tsakalidis. Optimal deterministic algorithms for 2-d and 3-d shallow cuttings. Discrete & Computational Geometry, 56(4):866-881, 2016. Google Scholar
  16. Chandra Chekuri, Sariel Har-Peled, and Kent Quanrud. Fast LP solving and approximation algorithms for geometric packing and covering problems. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1019-1038, 2020. Google Scholar
  17. Chandra Chekuri and Kent Quanrud. Randomized MWU for positive LPs. In Proceedings of the 29th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 358-377, 2018. Google Scholar
  18. Kenneth L. Clarkson. Algorithms for polytope covering and approximation. In Workshop on Algorithms and Data Structures, pages 246-252, 1993. Google Scholar
  19. Kenneth L. Clarkson and Kasturi Varadarajan. Improved approximation algorithms for geometric set cover. Discrete & Computational Geometry, 37(1):43-58, 2007. Google Scholar
  20. Alon Efrat, Matthew J. Katz, Frank Nielsen, and Micha Sharir. Dynamic data structures for fat objects and their applications. Computational Geometry, 15(4):215-227, 2000. URL: https://doi.org/10.1016/S0925-7721(99)00059-0.
  21. Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM (JACM), 32(1):130-136, 1985. URL: https://doi.org/10.1145/2455.214106.
  22. Christos Koufogiannakis and Neal E. Young. A nearly linear-time PTAS for explicit fractional packing and covering linear programs. Algorithmica, 70(4):648-674, 2014. URL: https://doi.org/10.1007/s00453-013-9771-6.
  23. Jiří Matoušek. Reporting points in halfspaces. Computational Geometry, 2(3):169-186, 1992. Google Scholar
  24. Jiří Matoušek, Raimund Seidel, and Emo Welzl. How to net a lot with little: Small ε-nets for disks and halfspaces. In Proceedings of the 6th Symposium on Computational Geometry (SoCG), pages 16-22, 1990. Google Scholar
  25. Nabil H. Mustafa. Computing optimal epsilon-nets is as easy as finding an unhit set. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pages 87:1-87:12, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.87.
  26. Nabil H. Mustafa, Rajiv Raman, and Saurabh Ray. Quasi-polynomial time approximation scheme for weighted geometric set cover on pseudodisks and halfspaces. SIAM J. Comput., 44(6):1650-1669, 2015. URL: https://doi.org/10.1137/14099317X.
  27. Nabil H. Mustafa and Saurabh Ray. PTAS for geometric hitting set problems via local search. In Proceedings of the 25th Symposium on Computational Geometry (SoCG), pages 17-22, 2009. Google Scholar
  28. János Pach and Gábor Tardos. Tight lower bounds for the size of epsilon-nets. In Proceedings of the 27th Symposium on Computational Geometry (SoCG), pages 458-463, 2011. URL: https://doi.org/10.1145/1998196.1998271.
  29. Evangelia Pyrga and Saurabh Ray. New existence proofs for ε-nets. In Proceedings of the 24th Symposium on Computational Geometry (SoCG), pages 199-207, 2008. URL: https://doi.org/10.1145/1377676.1377708.
  30. Edgar A. Ramos. On range reporting, ray shooting and k-level construction. In Proceedings of the 15th Symposium on Computational Geometry (SoCG), pages 390-399, 1999. Google Scholar
  31. Kasturi Varadarajan. Weighted geometric set cover via quasi-uniform sampling. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pages 641-648, 2010. Google Scholar
  32. Kasturi R. Varadarajan. Epsilon nets and union complexity. In Proceedings of the 25th Symposium on Computational Geometry (SoCG), pages 11-16, 2009. URL: https://doi.org/10.1145/1542362.1542366.
  33. Neal E. Young. Sequential and parallel algorithms for mixed packing and covering. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 538-546, 2001. URL: https://doi.org/10.1109/SFCS.2001.959930.
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