Quasi-polynomial time approximation scheme for sparse subsets of polygons

DOI10.1145/2582112.2582157MaRDI QIDQ4635534zbMATH OpenOpenAlexFDO

Authors Sariel Har-Peled

Publication date 23 April 2018

Published in Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.1369

zbMATH Keywords

approximation algorithmsindependent setQPTAS

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: We describe how to approximate, in quasi-polynomial time, the largest independent set of polygons, in a given set of polygons. Our algorithm works by extending the result of Adamaszek and Wiese cite{aw-asmwi-13, aw-qmwis-14} to polygons of arbitrary complexity. Surprisingly, the algorithm also works or computing the largest subset of the given set of polygons that has some sparsity condition. For example, we show that one can approximate the largest subset of polygons, such that the intersection graph of the subset does not contain a cycle of length $4$ (i.e., $K_{2,2}$).

Recommendations

• Approximation schemes for independent set and sparse subsets of polygons
• A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices
• Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
• Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking
• Independent Set of Convex Polygons: from \(n^{\epsilon }\) to \(1+\epsilon\) via shrinking

Cited in

(19)

• Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
• Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
• A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set
• Approximation algorithms for polynomial-expansion and low-density graphs
• An improvement of the parameterized frequent directions algorithm
• Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking
• Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking
• Packing and covering with non-piercing regions
• Optimality program in segment and string graphs
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Approximation schemes for independent set and sparse subsets of polygons
• Approximating multidimensional subset sum and Minkowski decomposition of polygons
• Local search strikes again: PTAS for variants of geometric covering and packing
• Efficient approximation schemes for uniform-cost clustering problems in planar graphs
• Literature survey on low rank approximation of matrices
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• A QPTAS for the base of the number of crossing-free structures on a planar point set
• A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices
• Anchored rectangle and square packings

This page was built for publication: Quasi-polynomial time approximation scheme for sparse subsets of polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635534)