Effectiveness of Local Search for Geometric Optimization
Vincent Cohen-Addad, Claire Mathieu · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2015
What is the effectiveness of local search algorithms for geometric problems in the plane? We prove that local search with neighborhoods of magnitude 1/epsilon^c is an approximation scheme for the following problems in the Euclidean plane: TSP with random inputs, Steiner tree with random inputs, uniform facility location (with worst case inputs), and bicriteria k-median (also with worst case inputs). The randomness assumption is necessary for TSP.