Approximation Schemes for Geometric Coverage Problems

Authors Steven Chaplick , Minati De , Alexander Ravsky, Joachim Spoerhase



PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.17.pdf
  • Filesize: 0.55 MB
  • 15 pages

Document Identifiers

Author Details

Steven Chaplick
  • Lehrstuhl für Informatik I, Universität Würzburg, Germany
Minati De
  • Department of Mathematics, Indian Institute of Technology Delhi, India
Alexander Ravsky
  • Pidstryhach Institute for Applied Problems of Mechanics and Mathematics, National Academy of Science of Ukraine, Lviv, Ukraine
Joachim Spoerhase
  • Lehrstuhl für Informatik I, Universität Würzburg, Germany
  • and , Institute of Computer Science, University of Wrocław, Poland

Cite AsGet BibTex

Steven Chaplick, Minati De, Alexander Ravsky, and Joachim Spoerhase. Approximation Schemes for Geometric Coverage Problems. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ESA.2018.17

Abstract

In their seminal work, Mustafa and Ray [Nabil H. Mustafa and Saurabh Ray, 2010] showed that a wide class of geometric set cover (SC) problems admit a PTAS via local search - this is one of the most general approaches known for such problems. Their result applies if a naturally defined "exchange graph" for two feasible solutions is planar and is based on subdividing this graph via a planar separator theorem due to Frederickson [Greg N. Frederickson, 1987]. Obtaining similar results for the related maximum coverage problem (MC) seems non-trivial due to the hard cardinality constraint. In fact, while Badanidiyuru, Kleinberg, and Lee [Ashwinkumar Badanidiyuru et al., 2012] have shown (via a different analysis) that local search yields a PTAS for two-dimensional real halfspaces, they only conjectured that the same holds true for dimension three. Interestingly, at this point it was already known that local search provides a PTAS for the corresponding set cover case and this followed directly from the approach of Mustafa and Ray. In this work we provide a way to address the above-mentioned issue. First, we propose a color-balanced version of the planar separator theorem. The resulting subdivision approximates locally in each part the global distribution of the colors. Second, we show how this roughly balanced subdivision can be employed in a more careful analysis to strictly obey the hard cardinality constraint. More specifically, we obtain a PTAS for any "planarizable" instance of MC and thus essentially for all cases where the corresponding SC instance can be tackled via the approach of Mustafa and Ray. As a corollary, we confirm the conjecture of Badanidiyuru, Kleinberg, and Lee [Ashwinkumar Badanidiyuru et al., 2012] regarding real halfspaces in dimension three. We feel that our ideas could also be helpful in other geometric settings involving a cardinality constraint.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
Keywords
  • balanced separators
  • maximum coverage
  • local search
  • approximation scheme
  • geometric approximation algorithms

Metrics

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

References

  1. Alexander A. Ageev and Maxim Sviridenko. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. Comb. Optim., 8(3):307-328, 2004. URL: http://dx.doi.org/10.1023/B:JOCO.0000038913.96607.c2.
  2. Noga Alon, Paul Seymour, and Robin Thomas. A separator theorem for nonplanar graphs. J. of the American Mathematical Society, 3:801-808, 1990. URL: http://dx.doi.org/10.1090/S0894-0347-1990-1065053-0.
  3. Rom Aschner, Matthew J. Katz, Gila Morgenstern, and Yelena Yuditsky. Approximation schemes for covering and packing. In 7th Int. Workshop on Algorithms and Computation (WALCOM'13), pages 89-100, 2013. Google Scholar
  4. Ashwinkumar Badanidiyuru, Robert Kleinberg, and Hooyeon Lee. Approximating low-dimensional coverage problems. In Symp. Computational Geometry (SoCG'12), pages 161-170, 2012. URL: http://dx.doi.org/10.1145/2261250.2261274.
  5. Sayan Bandyapadhyay and Kasturi R. Varadarajan. On variants of k-means clustering. In 32nd Symp. Computational Geometry (SoCG'16), pages 14:1-14:15, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.14.
  6. 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.
  7. Sergio Cabello and David Gajser. Simple PTAS’s for families of graphs excluding a minor. Discrete Applied Mathematics, 189:41-48, 2015. Google Scholar
  8. Timothy M. Chan, Elyot Grant, Jochen Könemann, and Malcolm Sharpe. Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In 23rd ACM-SIAM Symp. Discrete Algorithms (SODA'12), pages 1576-1585, 2012. URL: http://dl.acm.org/citation.cfm?id=2095116.2095241.
  9. Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. In 25th ACM Symp. Computational Geometry (SoCG'09), pages 333-340, 2009. URL: http://dx.doi.org/10.1145/1542362.1542420.
  10. 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: http://dx.doi.org/10.1007/s00454-012-9417-5.
  11. 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. In 57th IEEE Symp. Foundations of Computer Science (FOCS'16), pages 353-364, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.46.
  12. Vincent Cohen-Addad and Claire Mathieu. Effectiveness of local search for geometric optimization. In 31st Symp. Computational Geometry (SoCG'15), pages 329-343, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.SOCG.2015.329.
  13. Gérard Cornuéjols, George L. Nemhauser, and Laurence A. Wolsey. Worst-case and probabilistic analysis of algorithms for a location problem. Operations Research, 28(4):847-858, 1980. URL: http://dx.doi.org/10.1287/opre.28.4.847.
  14. Minati De and Abhiruk Lahiri. Geometric dominating set and set cover via local search. CoRR, abs/1605.02499, 2016. URL: http://arxiv.org/abs/1605.02499,
  15. Thomas Erlebach and Erik Jan van Leeuwen. Approximating geometric coverage problems. In 19th ACM-SIAM Symp. Discrete Algorithms (SODA'08), pages 1267-1276, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347220.
  16. Uriel Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634-652, 1998. URL: http://dx.doi.org/10.1145/285055.285059.
  17. Greg N. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput., 16(6):1004-1022, 1987. Google Scholar
  18. Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour. Local search yields a PTAS for k-means in doubling metrics. In 57th IEEE Symp. Foundations of Computer Science (FOCS'16), pages 365-374, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.47.
  19. Matt Gibson and Imran A. Pirwani. Algorithms for dominating set in disk graphs: Breaking the logn barrier - (extended abstract). In 18th European Symp. Algorithms (ESA'10), pages 243-254, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15775-2_21.
  20. Sathish Govindarajan, Rajiv Raman, Saurabh Ray, and Aniket Basu Roy. Packing and covering with non-piercing regions. In 24th European Symp. Algorithms (ESA'16), pages 47:1-47:17, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.47.
  21. Sariel Har-Peled and Kent Quanrud. Approximation algorithms for polynomial-expansion and low-density graphs. In 23rd European Symp. Algorithms (ESA'15), pages 717-728, 2015. Google Scholar
  22. Venky Harinarayan, Anand Rajaraman, and Jeffrey D. Ullman. Implementing data cubes efficiently. In ACM SIGMOD Int. Conference on Management of Data (ICDM'96), pages 205-216, 1996. URL: http://dx.doi.org/10.1145/233269.233333.
  23. Monika Rauch Henzinger, Philip N. Klein, Satish Rao, and Sairam Subramanian. Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci., 55(1):3-23, 1997. URL: http://dx.doi.org/10.1006/jcss.1997.1493.
  24. R. B. O. Kerkkamp and Karen Aardal. A constructive proof of swap local search worst-case instances for the maximum coverage problem. Oper. Res. Lett., 44(3):329-335, 2016. URL: http://dx.doi.org/10.1016/j.orl.2016.03.001.
  25. Philip N. Klein, Shay Mozes, and Christian Sommer. Structured recursive separator decompositions for planar graphs in linear time. In 45th Symp. Theory of Computing (STOC'13), pages 505-514, 2013. URL: http://dx.doi.org/10.1145/2488608.2488672.
  26. Erik Krohn, Matt Gibson, Gaurav Kanade, and Kasturi R. Varadarajan. Guarding terrains via local search. J. of Computational Geometry, 5(1):168-178, 2014. URL: http://jocg.org/index.php/jocg/article/view/128.
  27. Richard J Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM J. on Applied Mathematics, 36(2):177-189, 1979. URL: http://dx.doi.org/10.1137/0136016.
  28. Steffen Mecke and Dorothea Wagner. Solving geometric covering problems by data reduction. In 12th European Symp. Algorithms (ESA'04), pages 760-771, 2004. URL: http://dx.doi.org/10.1007/978-3-540-30140-0_67.
  29. 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(1):1650-1669, 2015. URL: http://dx.doi.org/10.1137/14099317X.
  30. Nabil H. Mustafa and Saurabh Ray. Improved results on geometric hitting set problems. Discrete & Computational Geometry, 44(4):883-895, 2010. Google Scholar
  31. Erez Petrank. The hardness of approximation: Gap location. Comput. Complexity, 4:133-157, 1994. URL: http://dx.doi.org/10.1007/BF01202286.
  32. Neil Robertson and Paul D Seymour. Graph minors. xx. wagner’s conjecture. J. of Combinatorial Theory, Series B, 92(2):325-357, 2004. URL: http://dx.doi.org/10.1016/j.jctb.2004.08.001.
  33. Kasturi R. Varadarajan. Weighted geometric set cover via quasi-uniform sampling. In 42nd ACM Symp. Theory of Computing (STOC'10), pages 641-648, 2010. URL: http://dx.doi.org/10.1145/1806689.1806777.
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