The Unreasonable Success of Local Search: Geometric Optimization

Vincent Cohen-Addad, Claire Mathieu

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 sch…