A tight analysis of geometric local search
DOI10.1007/S00454-021-00343-YzbMATH Open1497.68572OpenAlexW4206135143MaRDI QIDQ2117344FDOQ2117344
Authors: 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
Recommendations
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
- An inequality related to the isoperimetric inequality
- Unit disk graphs
- Fast approximation algorithms for a nonconvex covering problem
- Title not available (Why is that?)
- Improved results on geometric hitting set problems
- A Separator Theorem for Nonplanar Graphs
- Sparsity. Graphs, structures, and algorithms
- On the efficiency of polynomial time approximation schemes
- Independent set of intersection graphs of convex objects in 2D
- Separators for sphere-packings and nearest neighbor graphs
- Local Search Heuristics for k-Median and Facility Location Problems
- Exact algorithms and APX-hardness results for geometric packing and covering problems
- Algorithms – ESA 2005
- Title not available (Why is that?)
- Approximation algorithms for maximum independent set of pseudo-disks
- Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
- An Approximation Scheme for Terrain Guarding
- Simple PTAS's for families of graphs excluding a minor
- Parameterized Complexity of Independence and Domination on Geometric Graphs
- Packing and covering with non-piercing regions
- Approximation Schemes for Covering and Packing
- Limits of local search: quality and efficiency
- Geometric packing under non-uniform constraints
- Planar Support for Non-piercing Regions and Applications
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs
Cited In (6)
- Effectiveness of local search for geometric optimization
- Improved local search for geometric hitting set
- Optimality of geometric local search
- Local search strikes again: PTAS for variants of geometric covering and packing
- Local search: is brute-force avoidable?
- Limits of local search: quality and efficiency
This page was built for publication: A tight analysis of geometric local search
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117344)
