A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices
From MaRDI portal
Publication:5384010
DOI10.1137/1.9781611973402.49zbMath1422.68229arXiv1307.4257OpenAlexW2949272645WikidataQ58203668 ScholiaQ58203668MaRDI QIDQ5384010
Publication date: 20 June 2019
Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1307.4257
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items
A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set, Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, On the geometric priority set cover problem, Geometric dominating-set and set-cover via local-search, Geometric stabbing via threshold rounding and factor revealing LPs, 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, Independent set of convex polygons: from \(n^{\epsilon}\) to \(1+\epsilon \) via shrinking, Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs, Packing and covering with non-piercing regions, Anchored rectangle and square packings, Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs, Optimality program in segment and string graphs, Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking
