Document Open Access Logo

On Geometric Set Cover for Orthants

Authors Karl Bringmann, Sándor Kisfaludi-Bak, Michał Pilipczuk, Erik Jan van Leeuwen

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.26.pdf
  • Filesize: 1.01 MB
  • 18 pages

Document Identifiers

Author Details

Karl Bringmann
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
Sándor Kisfaludi-Bak
  • Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, The Netherlands
Michał Pilipczuk
  • Institute of Informatics, University of Warsaw, Poland
Erik Jan van Leeuwen
  • Dept. Information & Computing Sciences, Utrecht University, Utrecht, The Netherlands

Funding

  • Kisfaludi-Bak, Sándor: Supported by the Netherlands Organization for Scientific Research NWO under project no. 024.002.003.
  • Pilipczuk, Michał: This work is a part of project TOTAL (Mi. Pilipczuk) that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 677651).

Acknowledgements

We are grateful to an anonymous reviewer who pointed to us the reduction of Pach and Tardos [János Pach and Gábor Tardos, 2011] from ORTHANT COVER to GEOMETRIC SET COVER for half-spaces, and who suggested taking a closer look at the case of GEOMETRIC SET COVER for half-spaces. We would like to also thank the reviewer for pointing out that a PTAS for ORTHANT COVER in dimension $3$ follows from the work of Mustafa and Ray [Nabil H. Mustafa and Saurabh Ray, 2010] composed with the reduction of Pach and Tardos [János Pach and Gábor Tardos, 2011], which replaced our previous ad-hoc argument. We thank the organizers of the workshop on fixed-parameter computational geometry, held in May 2018 at Lorentz Center in Leiden, the Netherlands, where the main conceptual part of this work was done.

Cite As Get BibTex

Karl Bringmann, Sándor Kisfaludi-Bak, Michał Pilipczuk, and Erik Jan van Leeuwen. On Geometric Set Cover for Orthants. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.26

Abstract

We study SET COVER for orthants: Given a set of points in a d-dimensional Euclidean space and a set of orthants of the form (-infty,p_1] x ... x (-infty,p_d], select a minimum number of orthants so that every point is contained in at least one selected orthant. This problem draws its motivation from applications in multi-objective optimization problems. While for d=2 the problem can be solved in polynomial time, for d>2 no algorithm is known that avoids the enumeration of all size-k subsets of the input to test whether there is a set cover of size k. Our contribution is a precise understanding of the complexity of this problem in any dimension d >= 3, when k is considered a parameter: 
- For d=3, we give an algorithm with runtime n^O(sqrt{k}), thus avoiding exhaustive enumeration. 
- For d=3, we prove a tight lower bound of n^Omega(sqrt{k}) (assuming ETH). 
- For d >=slant 4, we prove a tight lower bound of n^Omega(k) (assuming ETH). 
 Here n is the size of the set of points plus the size of the set of orthants. The first statement comes as a corollary of a more general result: an algorithm for SET COVER for half-spaces in dimension 3. In particular, we show that given a set of points U in R^3, a set of half-spaces D in R^3, and an integer k, one can decide whether U can be covered by the union of at most k half-spaces from D in time |D|^O(sqrt{k})* |U|^O(1).
We also study approximation for SET COVER for orthants. While in dimension 3 a PTAS can be inferred from existing results, we show that in dimension 4 and larger, there is no 1.05-approximation algorithm with runtime f(k)* n^o(k) for any computable f, where k is the optimum.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Set Cover
  • parameterized complexity
  • algorithms
  • Exponential Time Hypothesis

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. In Siu-Wing Cheng and Olivier Devillers, editors, 30th Annual Symposium on Computational Geometry, SOCG'14, Kyoto, Japan, June 08 - 11, 2014, page 271. ACM, 2014. Google Scholar
  2. 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. Google Scholar
  3. Rom Aschner, Matthew J. Katz, Gila Morgenstern, and Yelena Yuditsky. Approximation Schemes for Covering and Packing. In Subir Kumar Ghosh and Takeshi Tokuyama, editors, WALCOM: Algorithms and Computation, 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings, volume 7748 of Lecture Notes in Computer Science, pages 89-100. Springer, 2013. Google Scholar
  4. Wolf-Tilo Balke, Ulrich Güntzer, and Jason Xin Zheng. Efficient Distributed Skylining for Web Information Systems. In Advances in Database Technology, EDBT'04, 9th International Conference on Extending Database Technology, volume 2992 of LNCS, pages 256-273. Springer, 2004. Google Scholar
  5. René Beier and Berthold Vöcking. Random knapsack in expected polynomial time. J. Comput. Syst. Sci., 69(3):306-329, 2004. Google Scholar
  6. Karl Bringmann, Tobias Friedrich, and Patrick Klitzke. Generic Postprocessing via Subset Selection for Hypervolume and Epsilon-Indicator. In 13th International Conference on Parallel Problem Solving from Nature, PPSN XIII, volume 8672 of LNCS, pages 518-527. Springer, 2014. Google Scholar
  7. Karl Bringmann, Tobias Friedrich, and Patrick Klitzke. Two-dimensional subset selection for hypervolume and epsilon-indicator. In Genetic and Evolutionary Computation Conference, GECCO'14, pages 589-596. ACM, 2014. Google Scholar
  8. Hervé Brönnimann and Michael T. Goodrich. Almost Optimal Set Covers in Finite VC-Dimension. Discrete and Computational Geometry, 14(1):463-479, 1995. URL: https://doi.org/10.1007/BF02570718.
  9. Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS'17, pages 743-754, 2017. Google Scholar
  10. Timothy M. Chan and Elyot Grant. Exact algorithms and APX-hardness results for geometric packing and covering problems. Comput. Geom., 47(2):112-124, 2014. 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 Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1576-1585. SIAM, 2012. Google Scholar
  12. Timothy M. Chan, Kasper Green Larsen, and Mihai Patrascu. Orthogonal Range Searching on the RAM, Revisited. CoRR, abs/1103.5510, 2011. URL: http://arxiv.org/abs/1103.5510.
  13. Vasek Chvátal. A Greedy Heuristic for the Set-Covering Problem. Mathematics of Operations Research, 4(3):233-235, 1979. URL: https://doi.org/10.1287/moor.4.3.233.
  14. Kenneth L. Clarkson and Kasturi R. Varadarajan. Improved Approximation Algorithms for Geometric Set Cover. Discrete & Computational Geometry, 37(1):43-58, 2007. Google Scholar
  15. Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg, and Alan Roytman. The Bane of Low-Dimensionality Clustering. In 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'18, pages 441-456. SIAM, 2018. Google Scholar
  16. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  17. Ludwig Danzer, Branko Grünbaum, and Viktor Klee. Helly’s theorem and its relatives. In Proceedings of Symposia in Pure Mathematics, volume 7, pages 101-180, 1963. Google Scholar
  18. Mark de Berg, Sándor Kisfaludi-Bak, and Gerhard Woeginger. The complexity of Dominating Set in geometric intersection graphs. Theoretical Computer Science, 769:18-31, 2019. URL: https://doi.org/10.1016/j.tcs.2018.10.007.
  19. Irit Dinur. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity (ECCC), 23:128, 2016. URL: http://eccc.hpi-web.de/report/2016/128.
  20. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 624-633. ACM, 2014. Google Scholar
  21. Rod G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness. Congressus Numerantium, 87:161-178, 1992. Google Scholar
  22. Thomas Erlebach, Hans Kellerer, and Ulrich Pferschy. Approximating Multiobjective Knapsack Problems. Management Science, 48(12):1603-1612, 2002. Google Scholar
  23. Thomas Erlebach and Erik Jan van Leeuwen. PTAS for weighted set cover on unit squares. In Maria J. Serna, Ronen Shaltiel, Klaus Jansen, and José D. P. Rolim, editors, 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, volume 6302 of Lecture Notes in Computer Science, pages 166-177. Springer, 2010. Google Scholar
  24. Robert J. Fowler, Mike S. Paterson, and Steven L. Tanimoto. Optimal Packing and Covering in the Plane are NP-Complete. Information Processing Letters, 12(3):133-137, 1981. URL: https://doi.org/10.1016/0020-0190(81)90111-3.
  25. Sathish Govindarajan, Rajiv Raman, Saurabh Ray, and Aniket Basu Roy. Packing and Covering with Non-Piercing Regions. In Piotr Sankowski and Christos Zaroliagis, editors, 24th Annual European Symposium on Algorithms (ESA 2016), volume 57 of Leibniz International Proceedings in Informatics (LIPIcs), pages 47:1-47:17. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  26. Pierre Hansen. Bicriterion path problems. In Multiple Criteria Decision Making Theory and Application, pages 109-127. Springer, 1980. Google Scholar
  27. Sariel Har-Peled. Being Fat and Friendly is Not Enough. CoRR, abs/0908.2369, 2009. URL: http://arxiv.org/abs/0908.2369.
  28. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. Google Scholar
  29. David S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9(3):256-278, December 1974. URL: https://doi.org/10.1016/S0022-0000(74)80044-9.
  30. David S. Johnson. The NP-Completeness Column: An Ongoing Guide. Journal of Algorithms, 3(2):182-195, 1982. URL: https://doi.org/10.1016/0196-6774(82)90018-9.
  31. Sándor Kisfaludi-Bak, Jesper Nederlof, and Erik Jan van Leeuwen. Nearly ETH-tight algorithms for Planar Steiner Tree with terminals on Few Faces. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'19, 2019. to appear. Google Scholar
  32. Vladlen Koltun and Christos H. Papadimitriou. Approximately dominating representatives. Theoretical Computer Science, 371(3):148-154, 2007. Google Scholar
  33. Sören Laue. Geometric Set Cover and Hitting Sets for Polytopes in ℝ³. In Susanne Albers and Pascal Weil, editors, STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 21-23, 2008, Proceedings, volume 08001 of Dagstuhl Seminar Series, pages 479-490. Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany, 2008. URL: http://drops.dagstuhl.de/opus/volltexte/2008/1367.
  34. Lászlo Lovász. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13(4):383-390, 1975. URL: https://doi.org/10.1016/0012-365X(75)90058-8.
  35. Pasin Manurangsi and Prasad Raghavendra. A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP'17, volume 80 of LIPIcs, pages 78:1-78:15, 2017. Google Scholar
  36. Dániel Marx. Parameterized Complexity of Independence and Domination on Geometric Graphs. In Parameterized and Exact Computation, Second International Workshop, IWPEC, Proceedings, pages 154-165, 2006. URL: https://doi.org/10.1007/11847250_14.
  37. Dániel Marx. On the Optimality of Planar and Geometric Approximation Schemes. In 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS'07, pages 338-348, 2007. Google Scholar
  38. Dániel Marx. A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals. In Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings, Part I, volume 7391 of Lecture Notes in Computer Science, pages 677-688. Springer, 2012. Google Scholar
  39. Dániel Marx and Michał Pilipczuk. Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams. In ESA 2015, volume 9294 of Lecture Notes in Computer Science, pages 865-877. Springer, 2015. See https://arxiv.org/abs/1504.05476 for the full version.
  40. Dániel Marx and Anastasios Sidiropoulos. The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for d-dimensional geometric problems. In 30th Annual Symposium on Computational Geometry, SOCG'14, page 67. ACM, 2014. Google Scholar
  41. Jiří Matoušek, Raimund Seidel, and Emo Welzl. How to Net a Lot with Little: Small epsilon-Nets for Disks and Halfspaces. In Raimund Seidel, editor, Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, June 6-8, 1990, pages 16-22. ACM, 1990. Google Scholar
  42. Gary L. Miller. Finding Small Simple Cycle Separators for 2-Connected Planar Graphs. J. Comput. Syst. Sci., 32(3):265-279, 1986. Google Scholar
  43. 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. Google Scholar
  44. Nabil H. Mustafa and Saurabh Ray. Improved Results on Geometric Hitting Set Problems. Discrete & Computational Geometry, 44(4):883-895, 2010. URL: https://doi.org/10.1007/s00454-010-9285-9.
  45. Frank Neumann. Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem. European Journal of Operational Research, 181(3):1620-1629, 2007. Google Scholar
  46. János Pach and Gábor Tardos. Tight lower bounds for the size of epsilon-nets. In Symposium on Computational Geometry, pages 458-463. ACM, 2011. Google Scholar
  47. János Pach and Gerhard J. Woeginger. Some New Bounds for Epsilon-Nets. In Raimund Seidel, editor, Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, June 6-8, 1990, pages 10-15. ACM, 1990. Google Scholar
  48. Christos H. Papadimitriou and Mihalis Yannakakis. On the Approximability of Trade-offs and Optimal Access of Web Sources. In 41st Annual Symposium on Foundations of Computer Science, FOCS'00, pages 86-92. IEEE Computer Society, 2000. Google Scholar
  49. Christos H. Papadimitriou and Mihalis Yannakakis. Multiobjective Query Optimization. In 20th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS'01. ACM, 2001. Google Scholar
  50. Mihai Pătraşcu and Ryan Williams. On the possibility of faster SAT algorithms. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pages 1065-1075. SIAM, 2010. Google Scholar
  51. Franco P. Preparata and Michael Ian Shamos. Computational Geometry - An Introduction. Texts and Monographs in Computer Science. Springer, 1985. Google Scholar
  52. Anastasios Sidiropoulos, Kritika Singhal, and Vijay Sridhar. Fractal Dimension and Lower Bounds for Geometric Problems. In 34th International Symposium on Computational Geometry, SoCG'18, volume 99 of LIPIcs, pages 70:1-70:14, 2018. Google Scholar
  53. Warren D. Smith and Nicholas C. Wormald. Geometric Separator Theorem & Applications. In 39th Annual Symposium on Foundations of Computer Science, FOCS '98, November 8-11, 1998, Palo Alto, California, USA, pages 232-243. IEEE, 1998. Google Scholar
  54. Erik Jan van Leeuwen. Optimization and Approximation on Systems of Geometric Objects. PhD thesis, University of Amsterdam, 2009. Google Scholar
  55. Kasturi R. Varadarajan. Weighted geometric set cover via quasi-uniform sampling. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 641-648. ACM, 2010. Google Scholar
  56. Sergei Vassilvitskii and Mihalis Yannakakis. Efficiently computing succinct trade-off curves. Theoretical Computer Science, 348(2-3):334-356, 2005. Google Scholar
  57. Daniel Vaz, Luís Paquete, and Aníbal Ponte. A note on the ε-indicator subset selection. Theoretical Computer Science, 499:113-116, 2013. 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