Optimality of geometric local search
From MaRDI portal
Publication:5115816
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Analysis of algorithms (68W40)
Recommendations
Cites work
- A Separator Theorem for Nonplanar Graphs
- Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
- Algorithms – ESA 2005
- An Approximation Scheme for Terrain Guarding
- An inequality related to the isoperimetric inequality
- Approximation algorithms for maximum independent set of pseudo-disks
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Approximation Schemes for Covering and Packing
- Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs
- Exact algorithms and APX-hardness results for geometric packing and covering problems
- Fast approximation algorithms for a nonconvex covering problem
- Geometric packing under non-uniform constraints
- Improved results on geometric hitting set problems
- Independent set of intersection graphs of convex objects in 2D
- Limits of local search: quality and efficiency
- Local Search Heuristics for k-Median and Facility Location Problems
- Packing and covering with non-piercing regions
- Parameterized Complexity of Independence and Domination on Geometric Graphs
- Separators for sphere-packings and nearest neighbor graphs
- Simple PTAS's for families of graphs excluding a minor
- Sparsity. Graphs, structures, and algorithms
- Sphere packings, lattices and groups. With additional contributions by E. Bannai, R. E. Borcherds, J. Leech, S. P. Norton, A. M. Odlyzko, R. A. Parker, L. Queen and B. B. Venkov.
- Unit disk graphs
Cited in
(10)- A tight analysis of geometric local search
- On the geometric set multicover problem
- Constructing planar support for non-piercing regions
- Improved local search for geometric hitting set
- Local search: is brute-force avoidable?
- scientific article; zbMATH DE number 7300558 (Why is no real title available?)
- Limits of local search: quality and efficiency
- Effectiveness of local search for geometric optimization
- Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions.
- Geographically optimal similarity
This page was built for publication: Optimality of geometric local search
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115816)