TY - GEN

T1 - Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles

AU - Henzinger, Monika

AU - Neumann, Stefan

AU - Wiese, Andreas

N1 - Publisher Copyright:
© Monika Henzinger, Stefan Neumann, and Andreas Wiese; licensed under Creative Commons License CC-BY 36th International Symposium on Computational Geometry (SoCG 2020).

PY - 2020/6/1

Y1 - 2020/6/1

N2 - 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 + ε)2d-approximate solution in the unweighted case and a O(2d)-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 + ε) logd−1 N.

AB - 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 + ε)2d-approximate solution in the unweighted case and a O(2d)-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 + ε) logd−1 N.

KW - Approximation algorithms

KW - Dynamic algorithms

KW - Geometric intersection graphs

KW - Independent set

KW - Interval graphs

UR - http://www.scopus.com/inward/record.url?scp=85086500517&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2020.51

DO - 10.4230/LIPIcs.SoCG.2020.51

M3 - Conference contribution

AN - SCOPUS:85086500517

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 36th International Symposium on Computational Geometry, SoCG 2020

A2 - Cabello, Sergio

A2 - Chen, Danny Z.

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 36th International Symposium on Computational Geometry, SoCG 2020

Y2 - 23 June 2020 through 26 June 2020

ER -