Document Open Access Logo

Worst-Case Efficient Dynamic Geometric Independent Set

Authors Jean Cardinal , John Iacono , Grigorios Koumoutsos

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.25.pdf
  • Filesize: 0.7 MB
  • 15 pages

Document Identifiers

Author Details

Jean Cardinal
  • Université libre de Bruxelles (ULB), Brussels, Belgium
John Iacono
  • Université libre de Bruxelles (ULB), Brussels, Belgium
Grigorios Koumoutsos
  • Université libre de Bruxelles (ULB), Brussels, Belgium

Funding

  • Iacono, John: Supported by the Fonds de la Recherche Scientifique-FNRS under Grant no MISU F 6001 1.
  • Koumoutsos, Grigorios: Supported by the Fonds de la Recherche Scientifique-FNRS under a "Scientific Collaborator" grant.

Acknowledgements

We would like to thank Timothy Chan and Qizheng He for pointing out an error in the previous version of this paper.

Cite As Get BibTex

Jean Cardinal, John Iacono, and Grigorios Koumoutsos. Worst-Case Efficient Dynamic Geometric Independent Set. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ESA.2021.25

Abstract

We consider the problem of maintaining an approximate maximum independent set of geometric objects under insertions and deletions. We present a data structure that maintains a constant-factor approximate maximum independent set for broad classes of fat objects in d dimensions, where d is assumed to be a constant, in sublinear worst-case update time. This gives the first results for dynamic independent set in a wide variety of geometric settings, such as disks, fat polygons, and their high-dimensional equivalents. For axis-aligned squares and hypercubes, our result improves upon all (recently announced) previous works. We obtain, in particular, a dynamic (4+ε)-approximation for squares, with O(log⁴ n) worst-case update time. 
Our result is obtained via a two-level approach. First, we develop a dynamic data structure which stores all objects and provides an approximate independent set when queried, with output-sensitive running time. We show that via standard methods such a structure can be used to obtain a dynamic algorithm with amortized update time bounds. Then, to obtain worst-case update time algorithms, we develop a generic deamortization scheme that with each insertion/deletion keeps (i) the update time bounded and (ii) the number of changes in the independent set constant. We show that such a scheme is applicable to fat objects by showing an appropriate generalization of a separator theorem. 
Interestingly, we show that our deamortization scheme is also necessary in order to obtain worst-case update bounds: If for a class of objects our scheme is not applicable, then no constant-factor approximation with sublinear worst-case update time is possible. We show that such a lower bound applies even for seemingly simple classes of geometric objects including axis-aligned rectangles in the plane.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Data structures design and analysis
Keywords
  • Maximum independent set
  • deamortization
  • approximation

Metrics

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

Related Versions

References

  1. Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, and Barna Saha. Dynamic set cover: improved algorithms and lower bounds. In ACM SIGACT Symposium on Theory of Computing, STOC, pages 114-125, 2019. URL: https://doi.org/10.1145/3313276.3316376.
  2. Anna Adamaszek and Andreas Wiese. Approximation schemes for maximum weight independent set of rectangles. In Foundations of Computer Science (FOCS), pages 400-409. IEEE, 2013. URL: https://doi.org/10.1109/FOCS.2013.50.
  3. Pankaj K. Agarwal, Hsien-Chih Chang, Subhash Suri, Allen Xiao, and Jie Xue. Dynamic geometric set cover and hitting set. In 36th International Symposium on Computational Geometry, SoCG, pages 2:1-2:15, 2020. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.2.
  4. Pankaj K. Agarwal, Marc J. van Kreveld, and Subhash Suri. Label placement by maximum independent set in rectangles. In Proceedings of the 9th Canadian Conference on Computational Geometry, 1997. Google Scholar
  5. Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully dynamic maximal independent set with sublinear update time. In ACM SIGACT Symposium on Theory of Computing, STOC, pages 815-826, 2018. URL: https://doi.org/10.1145/3188745.3188922.
  6. Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully dynamic maximal independent set with sublinear in n update time. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1919-1936, 2019. URL: https://doi.org/10.1137/1.9781611975482.116.
  7. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan. Fully dynamic maximal independent set with polylogarithmic update time. In IEEE Symposium on Foundations of Computer Science, FOCS, pages 382-405, 2019. URL: https://doi.org/10.1109/FOCS.2019.00032.
  8. Piotr Berman, Bhaskar DasGupta, S. Muthukrishnan, and Suneeta Ramaswami. Improved approximation algorithms for rectangle tiling and packing. In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, pages 427-436, 2001. URL: http://dl.acm.org/citation.cfm?id=365411.365496.
  9. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. A new deterministic algorithm for dynamic set cover. In IEEE Symposium on Foundations of Computer Science, FOCS, pages 406-423, 2019. URL: https://doi.org/10.1109/FOCS.2019.00033.
  10. Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Xiaowei Wu. Dynamic set cover: Improved amortized and worst-case update time. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2537-2549, 2021. URL: https://doi.org/10.1137/1.9781611976465.150.
  11. Sayan Bhattacharya and Janardhan Kulkarni. Deterministically maintaining a (2+ε)-approximate minimum vertex cover in o(1/ε²) amortized update time. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1872-1885, 2019. URL: https://doi.org/10.1137/1.9781611975482.113.
  12. Sujoy Bhore, Jean Cardinal, John Iacono, and Grigorios Koumoutsos. Dynamic geometric independent set. CoRR, abs/2007.08643, 2020. URL: http://arxiv.org/abs/2007.08643.
  13. Parinya Chalermsook and Julia Chuzhoy. Maximum independent set of rectangles. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 892-901. SIAM, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496867.
  14. Parinya Chalermsook and Bartosz Walczak. Coloring and maximum weight independent set of rectangles. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pages 860-868, 2021. URL: https://doi.org/10.1137/1.9781611976465.54.
  15. Timothy M. Chan. Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms, pages 178-189, 2003. URL: https://doi.org/10.1016/S0196-6774(02)00294-8.
  16. Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. Discret. Comput. Geom., pages 373-392, 2012. Google Scholar
  17. Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. Discret. Comput. Geom., 48(2):373-392, 2012. Google Scholar
  18. Timothy M. Chan and Qizheng He. More dynamic data structures for geometric set cover with sublinear update time. In 36th International Symposium on Computational Geometry, SoCG, page In press, 2021. Google Scholar
  19. Shiri Chechik and Tianyi Zhang. Fully dynamic maximal independent set in expected poly-log update time. In IEEE Symposium on Foundations of Computer Science, FOCS, pages 370-381, 2019. URL: https://doi.org/10.1109/FOCS.2019.00031.
  20. Julia Chuzhoy and Alina Ene. On approximating maximum independent set of rectangles. In Foundations of Computer Science (FOCS), pages 820-829. IEEE, 2016. URL: https://doi.org/10.1109/FOCS.2016.92.
  21. Spencer Compton, Slobodan Mitrovic, and Ronitt Rubinfeld. New partitioning techniques and faster algorithms for approximate interval scheduling. CoRR, abs/2012.15002, 2020. URL: http://arxiv.org/abs/2012.15002.
  22. Alon Efrat, Matthew J. Katz, Frank Nielsen, and Micha Sharir. Dynamic data structures for fat objects and their applications. Comput. Geom., 15(4):215-227, 2000. URL: https://doi.org/10.1016/S0925-7721(99)00059-0.
  23. Thomas Erlebach, Klaus Jansen, and Eike Seidel. Polynomial-time approximation schemes for geometric intersection graphs. SIAM J. Comput., pages 1302-1323, 2005. URL: https://doi.org/10.1137/S0097539702402676.
  24. Robert J. Fowler, Mike Paterson, and Steven L. Tanimoto. Optimal packing and covering in the plane are np-complete. Inf. Process. Lett., pages 133-137, 1981. URL: https://doi.org/10.1016/0020-0190(81)90111-3.
  25. Fanica Gavril. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput., 1(2):180-187, 1972. URL: https://doi.org/10.1137/0201013.
  26. Alexander Gavruskin, Bakhadyr Khoussainov, Mikhail Kokho, and Jiamou Liu. Dynamic algorithms for monotonic interval scheduling problem. Theor. Comput. Sci., pages 227-242, 2015. URL: https://doi.org/10.1016/j.tcs.2014.09.046.
  27. Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi. Online and dynamic algorithms for set cover. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 537-550, 2017. URL: https://doi.org/10.1145/3055399.3055493.
  28. Johan Håstad. Clique is hard to approximate within n^1-ε. Acta Mathematica, 182(1):105-142, 1999. URL: https://doi.org/10.1007/BF02392825.
  29. 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, pages 51:1-51:14, 2020. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.51.
  30. Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM, pages 130-136, 1985. URL: https://doi.org/10.1145/2455.214106.
  31. Sanjeev Khanna, S. Muthukrishnan, and Mike Paterson. On approximating rectangle tiling and packing. In ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 384-393, 1998. URL: http://dl.acm.org/citation.cfm?id=314613.314768.
  32. Madhav V. Marathe, H. Breu, Harry B. Hunt III, S. S. Ravi, and Daniel J. Rosenkrantz. Simple heuristics for unit disk graphs. Networks, 25(2):59-68, 1995. URL: https://doi.org/10.1002/net.3230250205.
  33. Joseph S. B. Mitchell. Approximating maximum independent set for rectangles in the plane. CoRR, abs/2101.00326, 2021. URL: http://arxiv.org/abs/2101.00326.
  34. Warren D. Smith and Nicholas C. Wormald. Geometric separator theorems & applications. In 39th Annual Symposium on Foundations of Computer Science, FOCS '98, November 8-11, 1998, Palo Alto, California, USA, pages 232-243. IEEE Computer Society, 1998. URL: https://doi.org/10.1109/SFCS.1998.743449.
  35. Bram Verweij and Karen Aardal. An optimisation algorithm for maximum independent set with applications in map labelling. In Algorithms - ESA '99, 7th Annual European Symposium, Prague, Czech Republic, July 16-18, 1999, Proceedings, pages 426-437, 1999. URL: https://doi.org/10.1007/3-540-48481-7_37.
  36. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput., pages 103-128, 2007. URL: https://doi.org/10.4086/toc.2007.v003a006.
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