How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking

DOI10.4230/LIPIcs.APPROX-RANDOM.2015.43zbMath1375.68117OpenAlexW2289655550MaRDI QIDQ5351888

Anna Adamaszek, Andreas Wiese, Parinya Chalermsook

Publication date: 31 August 2017

Full work available at URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.43

zbMATH Keywords

independent setapproximation algorithmsPTASresource augmentationrectangle intersection graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items

Stochastic Makespan Minimization in Structured Set Systems (Extended Abstract), Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking, On the complexity of anchored rectangle packing, Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking