A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices

DOI10.1137/1.9781611973402.49zbMATH Open1422.68229arXiv1307.4257OpenAlexW2949272645WikidataQ58203668 ScholiaQ58203668MaRDI QIDQ5384010FDOQ5384010

Authors: Anna Adamaszek, Andreas Wiese 

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: The Maximum Weight Independent Set of Polygons problem is a fundamental problem in computational geometry. Given a set of weighted polygons in the 2-dimensional plane, the goal is to find a set of pairwise non-overlapping polygons with maximum total weight. Due to its wide range of applications, the MWISP problem and its special cases have been extensively studied both in the approximation algorithms and the computational geometry community. Despite a lot of research, its general case is not well-understood. Currently the best known polynomial time algorithm achieves an approximation ratio of n^(epsilon) [Fox and Pach, SODA 2011], and it is not even clear whether the problem is APX-hard. We present a (1+epsilon)-approximation algorithm, assuming that each polygon in the input has at most a polylogarithmic number of vertices. Our algorithm has quasi-polynomial running time. We use a recently introduced framework for approximating maximum weight independent set in geometric intersection graphs. The framework has been used to construct a QPTAS in the much simpler case of axis-parallel rectangles. We extend it in two ways, to adapt it to our much more general setting. First, we show that its technical core can be reduced to the case when all input polygons are triangles. Secondly, we replace its key technical ingredient which is a method to partition the plane using only few edges such that the objects stemming from the optimal solution are evenly distributed among the resulting faces and each object is intersected only a few times. Our new procedure for this task is not more complex than the original one, and it can handle the arising difficulties due to the arbitrary angles of the polygons. Note that already this obstacle makes the known analysis for the above framework fail. Also, in general it is not well understood how to handle this difficulty by efficient approximation algorithms.

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

Recommendations

• Approximation schemes for independent set and sparse subsets of polygons
• A note on a QPTAS for maximum weight triangulation of planar point sets
• Quasi-polynomial time approximation scheme for sparse subsets of polygons
• 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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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
• Approximation schemes for partitioning: convex decomposition and surface approximation
• 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
• A note on a QPTAS for maximum weight triangulation of planar point sets
• 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
• Independent Set of Convex Polygons: from \(n^{\epsilon }\) to \(1+\epsilon\) via shrinking
• On the geometric priority set cover problem
• Approximation schemes for independent set and sparse subsets of polygons
• Geometric dominating-set and set-cover via local-search
• 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
• Quasi-polynomial time approximation scheme for sparse subsets of polygons
• Geometric stabbing via threshold rounding and factor revealing LPs
• Anchored rectangle and square packings

This page was built for publication: A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices

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