The Unreasonable Success of Local Search: Geometric Optimization
Vincent Cohen-Addad, Claire Mathieu · arXiv (Cornell University) · 2014
What is the effectiveness of local search algorithms for geometric problems in the plane? We prove that local search with neighborhoods of magnitude $1/ε^c$ is an approximation scheme for the following problems in the Euclidian plane: TSP with random inputs, Steiner tree with random inputs, facility location (with worst case inputs), and bicriteria $k$-median (also with worst case inputs). The randomness assumption is necessary for TSP.