A tight analysis of geometric local search

DOI10.1007/S00454-021-00343-YMaRDI QIDQ2117344zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

local searchexpansionmatchingsHall's marriage theorem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• Optimality of geometric local search
• Limits of local search: quality and efficiency
• Improved local search for geometric hitting set
• PTAS for geometric hitting set problems via local search
• Approximation Schemes for Covering and Packing

Cites work

• scientific article; zbMATH DE number 1224949 (Why is no real title available?)
• scientific article; zbMATH DE number 3027510 (Why is no real title available?)
• 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 Polynomial-Expansion and Low-Density Graphs
• Approximation Schemes for Covering and Packing
• Approximation algorithms for maximum independent set of pseudo-disks
• 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
• On the efficiency of polynomial time approximation schemes
• Packing and covering with non-piercing regions
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Planar Support for Non-piercing Regions and Applications
• 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

(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)