Effectiveness of local search for geometric optimization

DOI10.4230/LIPICS.SOCG.2015.329zbMATH Open1378.68167arXiv1410.0553MaRDI QIDQ5368697FDOQ5368697

Claire Mathieu, Vincent Cohen-Addad

Publication date: 10 October 2017

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

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

zbMATH Keywords

TSPlocal searchfacility locationSteiner tree\(k\)-medianPTAS

Mathematics Subject Classification ID

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

Cited In (16)

• Title not available (Why is that?)
• Packing and covering with non-piercing regions
• Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
• Approximation algorithms for spherical \(k\)-means problem using local search scheme
• Efficiency of Local Search
• A Local-Search Algorithm for Steiner Forest
• Stability and Recovery for Independence Systems
• Effective Heuristic Techniques for Combined Robust Clustering Problem
• Local search strikes again: PTAS for variants of geometric covering and packing
• On the geometric set multicover problem
• Constructing planar support for non-piercing regions
• Geometric dominating-set and set-cover via local-search
• Light Euclidean Spanners with Steiner Points
• Local Search Yields a PTAS for $k$-Means in Doubling Metrics
• Lossy kernelization of same-size clustering
• Lossy kernelization of same-size clustering

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)