Campus Event Calendar

New for: D1

AG 1

AG Audience

English

Note: We use this to send email in the morning.

30 Minutes

Saarbrücken

In the \textsc{Maximum Independent Set of Objects} problem, we are given an $n$-vertex planar graph $G$ and a family $\mathcal{D}$ of $N$ \emph{objects}, where each object is a connected subgraph of $G$. The task is to find a subfamily $\mathcal{F} \subseteq \mathcal{D}$ of maximum cardinality that consists of pairwise disjoint objects. This problem is $\mathsf{NP}$-hard and is equivalent to the problem of finding the maximum number of pairwise disjoint polygons in a given family of polygons in the plane.

As shown by Adamaszek et al. (J. ACM '19), the problem admits a \emph{quasi-polynomial time approximation scheme} (QPTAS): a $(1-\varepsilon)$-approximation algorithm with running time \mbox{$2^{\mathrm{poly}(\log(N),1/\epsilon)} \cdot n^{\mathcal{O}(1)}$}. Nevertheless, to the best of our knowledge, in the polynomial-time regime only the trivial $\mathcal{O}(N)$-approximation is known for the problem in full generality. In the restricted setting where the objects are pseudolines in the plane, Fox and Pach (SODA '11) gave an $N^{\varepsilon}$-approximation algorithm with running time $N^{2^{\tilde{\mathcal{O}}(1/\varepsilon)}}$, for any $\varepsilon>0$.

In this work, we present an $\text{OPT}^{\varepsilon}$-approximation algorithm for the problem that runs in time $N^{\tilde{\mathcal{O}}(1/\varepsilon^2)} n^{\mathcal{O}(1)}$, for any $\varepsilon>0$, thus improving upon the result of Fox and Pach both in terms of generality and in terms of the running time. Our approach combines the methodology of \emph{Voronoi separators}, introduced by Marx and Pilipczuk (TALG '22), with a new analysis of the approximation factor.

Joint work with Jana Cslovjecsek and Michał Pilipczuk.

Nidhi Rathi

+49 681 9325 1134

--email hidden

Zoom

897 027 2575

passcode not visible

logged in users only

Uwe Brahm, 03/06/2024 00:33

Uwe Brahm, 03/05/2024 19:26

Uwe Brahm, 02/06/2024 18:22

Nidhi Rathi, 02/06/2024 15:55 -- Created document.

Uwe Brahm, 03/05/2024 19:26

Uwe Brahm, 02/06/2024 18:22

Nidhi Rathi, 02/06/2024 15:55 -- Created document.