The Unreasonable Success of Local Search: Geometric Optimization
Cohen-Addad, Vincent · Mathieu, Claire
Original · EN
What is the effectiveness of local search algorithms for geometric problems in the plane? We prove that local search with neighborhoods of magnitude 1/εᶜ 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.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.