Speaker: Vincent Viallat Cohen-Addad, Ecole Normale Superieure

Title : The Unreasonable Success of Local Search: Geometric Optimization

Abstract: 
---------
What is the effectiveness of local search algorithms for geometric problems 
in the plane?  We prove that a local search algorithm with neighborhoods of 
magnitude 1/\epsilon^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.

This is a joint work with Claire Mathieu.