English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the Maximum Independent Set of Objects problem, we are given an $n$-vertexplanar graph $G$ and a family $\mathcal{D}$ of $N$ objects, where each objectis a connected subgraph of $G$. The task is to find a subfamily $\mathcal{F}\subseteq \mathcal{D}$ of maximum cardinality that consists of pairwisedisjoint objects. This problem is $\mathsf{NP}$-hard and is equivalent to theproblem of finding the maximum number of pairwise disjoint polygons in a givenfamily 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 whose running time is bounded by$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. Inthe restricted setting where the objects are pseudolines in the plane, Fox andPach (SODA '11) gave an $N^{\varepsilon}$-approximation algorithm with runningtime $N^{2^{\tilde{\mathcal{O}}(1/\varepsilon)}}$, for any $\varepsilon>0$.  In this work, we present an $\text{OPT}^{\varepsilon}$-approximationalgorithm 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 termsof generality and in terms of the running time. Our approach combines themethodology of Voronoi separators, introduced by Marx and Pilipczuk (TALG '22),with a new analysis of the approximation factor.

A polynomial-time $\text{OPT}^\epsilon$-approximation algorithm for maximum independent set of connected subgraphs in a planar graph