A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices
From MaRDI portal
Publication:5384010
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)
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.
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
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
- A note on a QPTAS for maximum weight triangulation of planar point sets
- Approximation algorithms for polynomial-expansion and low-density graphs
- 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
- Anchored rectangle and square packings
- Geometric stabbing via threshold rounding and factor revealing LPs
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)
