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

(21)

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

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)