Document Open Access Logo

Packing and Covering with Non-Piercing Regions

Authors Sathish Govindarajan, Rajiv Raman, Saurabh Ray, Aniket Basu Roy

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.47.pdf
  • Filesize: 0.5 MB
  • 17 pages

Document Identifiers

Author Details

Sathish Govindarajan
Rajiv Raman
Saurabh Ray
Aniket Basu Roy

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.47

Abstract

In this paper, we design the first polynomial time approximation schemes for the Set Cover and Dominating Set problems when the underlying sets are non-piercing regions (which include pseudodisks). We show that the local
search algorithm that yields PTASs when the regions are disks [Aschner/Katz/Morgenstern/Yuditsky, WALCOM 2013; Gibson/Pirwani, 2005; Mustafa/Raman/Ray, 2015] can be extended to work for non-piercing regions. While such an extension is intuitive and natural, attempts to settle this question have failed even for pseudodisks. The techniques used for analysis when the regions are disks rely heavily on the underlying geometry, and do not extend to topologically defined settings such as pseudodisks. In order to prove our results, we introduce novel techniques that we believe will find applications in other problems. 

We then consider the Capacitated Region Packing problem. Here, the input consists of a set of points with capacities, and a set of regions. The objective is to pick a maximum cardinality subset of regions so that no point is covered by more regions than its capacity. We show that this problem admits a PTAS when the regions are k-admissible regions (pseudodisks are 2-admissible), and the capacities are bounded. Our result settles a conjecture of Har-Peled (see Conclusion of [Har-Peled, SoCG 2014]) in the affirmative. The conjecture was for a weaker version of the problem, namely when the regions are pseudodisks, the capacities are uniform, and the point set consists of all points in the plane.

Finally, we consider the Capacitated Point Packing problem. In this setting, the regions have capacities, and our
objective is to find a maximum cardinality subset of points such that no region has more points than its capacity. We show that this problem admits a PTAS when the capacity is unity, extending one of the results of Ene et al. [Ene/Har-Peled/Raichel, SoCG 2012].

Subject Classification

Keywords
  • Local Search
  • Set Cover
  • Dominating Set
  • Capacitated Packing
  • Approximation algorithms

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 and Nabil H. Mustafa. Independent set of intersection graphs of convex objects in 2D. Computational Geometry, 34(2):83-95, 2006. Google Scholar
  4. Pankaj K. Agarwal, Marc van Kreveld, and Subhash Suri. Label placement by maximum independent set in rectangles. Computational Geometry, 11(3):209-218, 1998. Google Scholar
  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. Franz Aurenhammer. Voronoi diagrams—a survey of a fundamental geometric data structure. ACM Computing Surveys (CSUR), 23(3):345-405, 1991. Google Scholar
  7. Reuven Bar-Yehuda, Danny Hermelin, and Dror Rawitz. Minimum vertex cover in rectangle graphs. Computational Geometry, 44(6):356-364, 2011. Google Scholar
  8. Vijay V. S. P. Bhattiprolu and Sariel Har-Peled. Separating a Voronoi Diagram via Local Search. In Proceedings of the Thirty-second International Symposium on Computational Geometry, SoCG'16, pages 18:1-18:16, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  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. Timothy M. Chan. Polynomial-time approximation schemes for packing and piercing fat objects. Journal of Algorithms, 46(2):178-189, 2003. Google Scholar
  11. 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
  12. 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
  13. 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
  14. Jeffrey S. Doerschler and Herbert Freeman. A rule-based system for dense-map name placement. Communications of the ACM, 35(1):68-79, 1992. Google Scholar
  15. Stephane Durocher and Robert Fraser. Duality for geometric set cover and geometric hitting set problems on pseudodisks. In Proceedings of the 27th Canadian Conference on Computational Geometry, pages 8-16, 2015. Google Scholar
  16. Alina Ene, Sariel Har-Peled, and Benjamin Raichel. Geometric packing under non-uniform constraints. In Proceedings of the Twenty-eighth Annual Symposium on Computational Geometry, SoCG'12, pages 11-20, New York, NY, USA, 2012. ACM. Google Scholar
  17. Thomas Erlebach and Erik Jan van Leeuwen. Approximating geometric coverage problems. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete algorithms, SODA'08, pages 1267-1276, 2008. Google Scholar
  18. Guy Even, Dror Rawitz, and Shimon (Moni) Shahar. Hitting sets when the VC-dimension is small. Inf. Process. Lett., 95(2):358-362, July 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. Sariel Har-Peled. Quasi-polynomial time approximation scheme for sparse subsets of polygons. In Proceedings of the Thirtieth Annual Symposium on Computational Geometry, SoCG'14, pages 120-129, New York, NY, USA, 2014. ACM. Google Scholar
  21. Sariel Har-Peled and Kent Quanrud. Approximation algorithms for polynomial-expansion and low-density graphs. In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 717-728, 2015. Google Scholar
  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. 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
  24. Brian Lent, Arun Swami, and Jennifer Widom. Clustering association rules. In Proceedings of the Thirteenth International Conference on Data Engineering, pages 220-231. IEEE Computer Society, 1997. Google Scholar
  25. 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
  26. Jiří Matoušek. Lectures on Discrete Geometry. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2002. Google Scholar
  27. 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
  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. Evangelia Pyrga and Saurabh Ray. New existence proofs for ε-nets. In Proceedings of the Twenty-fourth Annual Symposium on Computational Geometry, SoCG'08, pages 199-207, New York, NY, USA, 2008. ACM. Google Scholar
  30. Di Tian and Nicolas D. Georganas. A coverage-preserving node scheduling scheme for large wireless sensor networks. In Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, pages 32-41. ACM, 2002. 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. Sue Whitesides and Rongyao Zhao. k-admissible collections of Jordan curves and offsets of circular arc figures. McGill University, School of Computer Science, 1990. 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 About DROPS Imprint Privacy Contact