Publication:5009574
From MaRDI portal
DOI10.4230/LIPIcs.ESA.2018.17MaRDI QIDQ5009574
Steven Chaplick, Joachim Spoerhase, Minati De, O. V. Ravskyj
Publication date: 4 August 2021
Full work available at URL: https://arxiv.org/abs/1607.06665
local search; approximation scheme; balanced separators; maximum coverage; geometric approximation algorithms
68Wxx: Algorithms in computer science
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for maximum independent set of pseudo-disks
- Improved results on geometric hitting set problems
- Graph minors. XX: Wagner's conjecture
- The hardness of approximation: Gap location
- A constructive proof of swap local search worst-case instances for the maximum coverage problem
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Almost optimal set covers in finite VC-dimension
- Simple PTAS's for families of graphs excluding a minor
- Approximating low-dimensional coverage problems
- Weighted geometric set cover via quasi-uniform sampling
- Guarding terrains via local search
- A threshold of ln n for approximating set cover
- Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- A Separator Theorem for Planar Graphs
- Worst-Case and Probabilistic Analysis of Algorithms for a Location Problem
- A Separator Theorem for Nonplanar Graphs
- Packing and Covering with Non-Piercing Regions
- Local Search Yields a PTAS for $k$-Means in Doubling Metrics
- Approximation Schemes for Covering and Packing
- Approximation algorithms for maximum independent set of pseudo-disks
- Algorithms – ESA 2004
- Structured recursive separator decompositions for planar graphs in linear time
- Faster shortest-path algorithms for planar graphs
