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 – ESA 2005
- Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
- 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
- scientific article; zbMATH DE number 1224949 (Why is no real title available?)
- 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
- 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)
