A tight analysis of geometric local search
From MaRDI portal
Publication:2117344
DOI10.1007/s00454-021-00343-yzbMath1497.68572OpenAlexW4206135143MaRDI QIDQ2117344
Bruno Jartoux, Nabil H. Mustafa
Publication date: 21 March 2022
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-021-00343-y
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the efficiency of polynomial time approximation schemes
- Exact algorithms and APX-hardness results for geometric packing and covering problems
- Sparsity. Graphs, structures, and algorithms
- Approximation algorithms for maximum independent set of pseudo-disks
- Limits of local search: quality and efficiency
- Improved results on geometric hitting set problems
- Unit disk graphs
- Simple PTAS's for families of graphs excluding a minor
- Independent set of intersection graphs of convex objects in 2D
- Geometric packing under non-uniform constraints
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Parameterized Complexity of Independence and Domination on Geometric Graphs
- Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
- An Approximation Scheme for Terrain Guarding
- Fast approximation algorithms for a nonconvex covering problem
- A Separator Theorem for Nonplanar Graphs
- Separators for sphere-packings and nearest neighbor graphs
- Packing and Covering with Non-Piercing Regions
- Local Search Heuristics for k-Median and Facility Location Problems
- Approximation Schemes for Covering and Packing
- Planar Support for Non-piercing Regions and Applications
- Algorithms – ESA 2005
- An inequality related to the isoperimetric inequality
This page was built for publication: A tight analysis of geometric local search
