Document Open Access Logo

Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles

Authors Monika Henzinger , Stefan Neumann, Andreas Wiese

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.51.pdf
  • Filesize: 488 kB
  • 14 pages

Document Identifiers

Author Details

Monika Henzinger
  • Faculty of Computer Science, University of Vienna, Austria
Stefan Neumann
  • Faculty of Computer Science, University of Vienna, Austria
Andreas Wiese
  • Department of Industrial Engineering, Universidad de Chile, Santiago, Chile

Funding

  • Henzinger, Monika: The research leading to these results has received funding from the European Research Council under the European Community’s Seventh Framework Programme (FP7/2007-2013) / ERC grant agreement No. 340506.
  • Neumann, Stefan: Part of this work was done while visiting Brown University. Stefan Neumann gratefully acknowledges the financial support from the Doctoral Programme "Vienna Graduate School on Computational Optimization" which is funded by the Austrian Science Fund (FWF, project no. W1260-N35). The research leading to these results has received funding from the European Research Council under the European Community’s Seventh Framework Programme (FP7/2007-2013) / ERC grant agreement No. 340506.
  • Wiese, Andreas: Andreas Wiese was supported by the grant Fondecyt Regular 1170223.

Acknowledgements

We are grateful to the anonymous reviewers for their helpful comments.

Cite As Get BibTex

Monika Henzinger, Stefan Neumann, and Andreas Wiese. Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SoCG.2020.51

Abstract

Independent set is a fundamental problem in combinatorial optimization. While in general graphs the problem is essentially inapproximable, for many important graph classes there are approximation algorithms known in the offline setting. These graph classes include interval graphs and geometric intersection graphs, where vertices correspond to intervals/geometric objects and an edge indicates that the two corresponding objects intersect. 
We present dynamic approximation algorithms for independent set of intervals, hypercubes and hyperrectangles in d dimensions. They work in the fully dynamic model where each update inserts or deletes a geometric object. All our algorithms are deterministic and have worst-case update times that are polylogarithmic for constant d and ε>0, assuming that the coordinates of all input objects are in [0, N]^d and each of their edges has length at least 1. We obtain the following results:  
- For weighted intervals, we maintain a (1+ε)-approximate solution. 
- For d-dimensional hypercubes we maintain a (1+ε)2^d-approximate solution in the unweighted case and a O(2^d)-approximate solution in the weighted case. Also, we show that for maintaining an unweighted (1+ε)-approximate solution one needs polynomial update time for d ≥ 2 if the ETH holds. 
- For weighted d-dimensional hyperrectangles we present a dynamic algorithm with approximation ratio (1+ε)log^{d-1}N.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
  • Theory of computation → Computational geometry
Keywords
  • Dynamic algorithms
  • independent set
  • approximation algorithms
  • interval graphs
  • geometric intersection graphs

Metrics

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

Related Versions

References

  1. Anna Adamaszek, Sariel Har-Peled, and Andreas Wiese. Approximation schemes for independent set and sparse subsets of polygons. J. Assoc. Comput. Mach., 66(4):29:1-29:40, June 2019. URL: https://doi.org/10.1145/3326122.
  2. Pankaj K. Agarwal, Marc J. van Kreveld, and Subhash Suri. Label placement by maximum independent set in rectangles. Comput. Geom., 11(3-4):209-218, 1998. Google Scholar
  3. Sanjeev Arora. Polynomial time approximation schemes for euclidean tsp and other geometric problems. In FOCS, pages 2-11, 1996. Google Scholar
  4. Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully dynamic maximal independent set with sublinear update time. In STOC, pages 815-826, 2018. Google Scholar
  5. Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully dynamic maximal independent set with sublinear in n update time. In SODA, pages 1919-1936. SIAM, 2019. Google Scholar
  6. Ainesh Bakshi, Nadiia Chepurko, and David P. Woodruff. Weighted maximum independent set of geometric objects in turnstile streams. CoRR, abs/1902.10328, 2019. URL: http://arxiv.org/abs/1902.10328.
  7. Soheil Behnezhad, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Cliff Stein, and Madhu Sudan. Fully dynamic maximal independent set with polylogarithmic update time. In FOCS, 2019. Google Scholar
  8. Sergio Cabello and Pablo Pérez-Lantero. Interval selection in the streaming model. Theor. Comput. Sci., 702:77-96, 2017. URL: https://doi.org/10.1016/j.tcs.2017.08.015.
  9. Parinya Chalermsook and Julia Chuzhoy. Maximum independent set of rectangles. In SODA, pages 892-901, 2009. Google Scholar
  10. Timothy M. Chan. Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms, 46(2):178-189, 2003. Google Scholar
  11. Timothy M Chan. A note on maximum independent sets in rectangle intersection graphs. Information Processing Letters, 89(1):19-23, 2004. 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, September 2012. URL: https://doi.org/10.1007/s00454-012-9417-5.
  13. Shiri Chechik and Tianyi Zhang. Fully dynamic maximal independent set in expected poly-log update time. In FOCS, 2019. Google Scholar
  14. Julia Chuzhoy and Alina Ene. On approximating maximum independent set of rectangles. In FOCS, pages 820-829, 2016. Google Scholar
  15. Yuhao Du and Hengjie Zhang. Improved algorithms for fully dynamic maximal independent set. CoRR, abs/1804.08908, 2018. URL: http://arxiv.org/abs/1804.08908.
  16. Herbert Edelsbrunner. A note on dynamic range searching. Bull. EATCS, 15(34-40):120, 1981. Google Scholar
  17. Yuval Emek, Magnús M. Halldórsson, and Adi Rosén. Space-constrained interval selection. ACM Trans. Algorithms, 12(4):51:1-51:32, 2016. Google Scholar
  18. Thomas Erlebach, Klaus Jansen, and Eike Seidel. Polynomial-time approximation schemes for geometric intersection graphs. SIAM Journal on Computing, 34(6):1302-1323, 2005. Google Scholar
  19. Robert J. Fowler, Michael 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.
  20. András Frank. Some polynomial algorithms for certain graphs and hypergraphs. In Proceedings of the 5th British Combinatorial Conference. Utilitas Mathematica, 1975. Google Scholar
  21. Alexander Gavruskin, Bakhadyr Khoussainov, Mikhail Kokho, and Jiamou Liu. Dynamic algorithms for monotonic interval scheduling problem. Theor. Comput. Sci., 562:227-242, 2015. Google Scholar
  22. Manoj Gupta and Shahbaz Khan. Simple dynamic algorithms for maximal independent set and other problems. CoRR, abs/1804.01823, 2018. URL: http://arxiv.org/abs/1804.01823.
  23. Monika Henzinger, Stefan Neumann, and Andreas Wiese. Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. CoRR, abs/2003.02605, 2020. URL: http://arxiv.org/abs/2003.02605.
  24. Dorit S Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and vlsi. J. ACM, 32(1):130-136, 1985. Google Scholar
  25. Sanjeev Khanna, S. Muthukrishnan, and Mike Paterson. On approximating rectangle tiling and packing. In SODA, pages 384-393, 1998. Google Scholar
  26. Jon M. Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 2006. Google Scholar
  27. D. T. Lee and Franco P. Preparata. Computational geometry - A survey. IEEE Trans. Computers, 33(12):1072-1101, 1984. Google Scholar
  28. Morteza Monemizadeh. Dynamic maximal independent set. CoRR, abs/1906.09595, 2019. URL: http://arxiv.org/abs/1906.09595.
  29. Bram Verweij and Karen Aardal. An optimisation algorithm for maximum independent set with applications in map labelling. In ESA, pages 426-437, 1999. Google Scholar
  30. Dan E. Willard and George S. Lueker. Adding range restriction capability to dynamic data structures. J. ACM, 32(3):597-617, 1985. Google Scholar
  31. D. Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3:103-128, 2007. 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