Can I read Dynamic Geometric Independent Set on EtoBox?

Dynamic Geometric Independent Set by Bhore, Sujoy; Cardinal, Jean; Iacono, John; Koumoutsos, Grigorios is a scholarly article available to read on EtoBox.

What is Dynamic Geometric Independent Set about?

We present fully dynamic approximation algorithms for the Maximum Independent Set problem on several types of geometric objects: intervals on the real line, arbitrary axis-aligned squares in the plane and axis-aligned $d$-dimensional hypercubes. It is known that a maximum independent set of a collection of $n$ intervals can be found in $O(n\log n)$ time, while it is already \textsf{NP}-hard for a set of unit squares. Moreover, the problem is inapproximable on many important graph families, but admits a \textsf{PTAS} for a set of arbitrary pseudo-disks. Therefore, a fundamental question in computational geometry is whether it is possible to maintain an approximate maximum independent set in a set of dynamic geometric objects, in truly sublinear time per insertion or deletion. In this work, we answer this question in the affirmative for intervals, squares and hypercubes. First, we show that for intervals a $(1+\varepsilon)$-approximate maximum independent set can be maintained with logarithmic worst-case update time. This is achieved by maintaining a locally optimal solution using a constant number of constant-size exchanges per update. We then show how our interval structure can be

Author

Bhore, Sujoy; Cardinal, Jean; Iacono, John; Koumoutsos, Grigorios

Published

2020

Language

EN