LIPIcs.ESA.2021.25.pdf
- Filesize: 0.7 MB
- 15 pages
Document
Worst-Case Efficient Dynamic Geometric Independent Set
Authors
Jean Cardinal 
,
John Iacono ,
-
Part of:
Volume:
29th Annual European Symposium on Algorithms (ESA 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-08-31
File
Document Identifiers
Author Details
Acknowledgements
We would like to thank Timothy Chan and Qizheng He for pointing out an
error in the previous version of this paper.
Cite AsGet 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
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)
0PDF Downloads
References
- 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.
- 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.
- 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.
-
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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
-
Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. Discret. Comput. Geom., pages 373-392, 2012.
-
Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. Discret. Comput. Geom., 48(2):373-392, 2012.
-
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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.