Quasi-polynomial time approximation scheme for sparse subsets of polygons

DOI10.1145/2582112.2582157zbMATH Open1395.68306arXiv1312.1369OpenAlexW2039079162MaRDI QIDQ4635534FDOQ4635534

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)

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}$).

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

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

zbMATH Keywords

approximation algorithmsindependent setQPTAS

Mathematics Subject Classification ID

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

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 schemes for independent set and sparse subsets of polygons
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• 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)