Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking
From MaRDI portal
Publication:1742371
DOI10.1007/s00453-017-0347-8zbMath1390.68733OpenAlexW2737247819WikidataQ59528414 ScholiaQ59528414MaRDI QIDQ1742371
Publication date: 11 April 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-017-0347-8
independent setconvex polygonsapproximation algorithmsPTASresource augmentationgeometric intersection graphsshrinking
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for maximum independent set of pseudo-disks
- Optimal packing and covering in the plane are NP-complete
- Unit disk graphs
- Label placement by maximum independent set in rectangles
- Fast stabbing of boxes in high dimensions
- Independent set of intersection graphs of convex objects in 2D
- Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
- Data Mining with optimized two-dimensional association rules
- Approximation schemes for covering and packing problems in image processing and VLSI
- Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons
- Constant Integrality Gap LP Formulations of Unsplittable Flow on a Path
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking
- A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices
- A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths
