A tight analysis of geometric local search

DOI10.1007/S00454-021-00343-YzbMATH Open1497.68572OpenAlexW4206135143MaRDI QIDQ2117344FDOQ2117344

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

• 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

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)

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 logn Barrier
• 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
• Title not available (Why is that?)

Cited In (1)

• Local search strikes again: PTAS for variants of geometric covering and packing

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)