Effectiveness of local search for geometric optimization

DOI10.4230/LIPICS.SOCG.2015.329MaRDI QIDQ5368697zbMATH OpenFDO

Authors Vincent Cohen-Addad, Claire Mathieu

Publication date 10 October 2017

Full work available at URL https://arxiv.org/abs/1410.0553

zbMATH Keywords

\(k\)-medianfacility locationlocal searchPTASSteiner treeTSP

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Optimality of geometric local search
• scientific article; zbMATH DE number 1857642
• A tight analysis of geometric local search
• Limits of local search: quality and efficiency
• Local search: complexity and approximation

Cited in

(18)

• Packing and covering with non-piercing regions
• Lossy kernelization of same-size clustering
• On the geometric set multicover problem
• Constructing planar support for non-piercing regions
• Approximation algorithms for spherical \(k\)-means problem using local search scheme
• Local search yields a PTAS for \(k\)-means in doubling metrics
• Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics
• A local-search algorithm for Steiner forest
• scientific article; zbMATH DE number 7378687 (Why is no real title available?)
• Stability and recovery for independence systems
• Efficiency of Local Search
• Light Euclidean Spanners with Steiner Points
• Local search strikes again: PTAS for variants of geometric covering and packing
• Effective Heuristic Techniques for Combined Robust Clustering Problem
• Geometric dominating-set and set-cover via local-search
• Lossy kernelization of same-size clustering
• On hypergraph supports (extended abstract)
• A fast algorithm for computing a planar support for non-piercing rectangles

This page was built for publication: Effectiveness of local search for geometric optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368697)