Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles
Henzinger MH, Neumann S, Wiese A. 2020. Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 51.
Download (ext.)
https://doi.org/10.4230/LIPIcs.SoCG.2020.51
[Published Version]
Conference Paper
| Published
| English
Scopus indexed
Author
Henzinger, MonikaISTA ;
Neumann, Stefan;
Wiese, Andreas
Series Title
LIPIcs
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.
Publishing Year
Date Published
2020-06-08
Proceedings Title
36th International Symposium on Computational Geometry
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume
164
Article Number
51
Conference
SoCG: Symposium on Computational Geometry
Conference Location
Zurich, Switzerland
Conference Date
2020-06-23 – 2020-06-26
ISBN
ISSN
IST-REx-ID
Cite this
Henzinger MH, Neumann S, Wiese A. Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.51
Henzinger, M. H., Neumann, S., & Wiese, A. (2020). Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. In 36th International Symposium on Computational Geometry (Vol. 164). Zurich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.51
Henzinger, Monika H, Stefan Neumann, and Andreas Wiese. “Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles.” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.51.
M. H. Henzinger, S. Neumann, and A. Wiese, “Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles,” in 36th International Symposium on Computational Geometry, Zurich, Switzerland, 2020, vol. 164.
Henzinger MH, Neumann S, Wiese A. 2020. Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 51.
Henzinger, Monika H., et al. “Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles.” 36th International Symposium on Computational Geometry, vol. 164, 51, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.51.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2003.02605