Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking

DOI10.4230/LIPICS.MFCS.2017.42zbMATH Open1441.68270arXiv1611.06501OpenAlexW2550398909MaRDI QIDQ5111257FDOQ5111257

Authors: Michał Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese 

Publication date: 26 May 2020

Abstract: Consider the Maximum Weight Independent Set problem for rectangles: given a family of weighted axis-parallel rectangles in the plane, find a maximum-weight subset of non-overlapping rectangles. The problem is notoriously hard both in the approximation and in the parameterized setting. The best known polynomial-time approximation algorithms achieve super-constant approximation ratios [Chalermsook and Chuzhoy, SODA 2009; Chan and Har-Peled, Discrete & Comp. Geometry 2012], even though there is a $(1+epsilon)$-approximation running in quasi-polynomial time [Adamaszek and Wiese, FOCS 2013; Chuzhoy and Ene, FOCS 2016]. When parameterized by the target size of the solution, the problem is $mathsfW[1]$-hard even in the unweighted setting [Marx, FOCS 2007]. To achieve tractability, we study the following shrinking model: one is allowed to shrink each input rectangle by a multiplicative factor $1-delta$ for some fixed $delta>0$, but the performance is still compared against the optimal solution for the original, non-shrunk instance. We prove that in this regime, the problem admits an EPTAS with running time $f(epsilon,delta)cdot{n}^{mathcalO(1)}$, and an FPT algorithm with running time $f(k,delta)cdot{n}^{mathcalO(1)}$, in the setting where a maximum-weight solution of size at most $k$ is to be computed. This improves and significantly simplifies a PTAS given earlier for this problem [Adamaszek et al., APPROX 2015], and provides the first parameterized results for the shrinking model. Furthermore, we explore kernelization in the shrinking model, by giving efficient kernelization procedures for several variants of the problem when the input rectangles are squares.

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

Recommendations

• How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking
• 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
• Approximation schemes for independent set and sparse subsets of polygons
• Maximum independent set of rectangles

zbMATH Keywords

combinatorial optimizationapproximation algorithmsfixed-parameter algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Linear degree extractors and the inapproximability of max clique and chromatic number
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Algorithms – ESA 2005
• Maximum independent set of rectangles
• Polynomial-time approximation schemes for packing and piercing fat objects
• Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• Approximation algorithms for maximum independent set of pseudo-disks
• Quasi-polynomial time approximation scheme for sparse subsets of polygons
• A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices
• How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking
• Independent Set of Convex Polygons: from \(n^{\epsilon }\) to \(1+\epsilon\) via shrinking
• Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking

Cited In (5)

• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking
• Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms
• 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

This page was built for publication: Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking

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