√ Abstract :

We present polynomial-time approximation schemes based on local search for facility location, k-median, and k-means in planar graphs or in Euclidean spaces of bounded dimension, where the local neighborhood of a solution consists of modifying the locations of a few centers.
This can be viewed as an explanation for the effectiveness of local search heuristics in practice.
This is based on joint work with Vincent Cohen-Addad and Philip Klein.

Bio :

Claire Mathieu works on algorithms, particularly the design of approximation schemes for NP-hard combinatorial optimization problems. She is employed by CNRS (Centre National de la Recherche Scientifique) in Paris, France. Her current research interests include approximation algorithms for planar graphs and for Euclidean problems; probabilistic models for social networks; hierarchies of semi-definite programming relaxations; network tomography; scheduling to minimize energy; online algorithms; computing with noisy information; facility location and clustering; and occasional forays into algorithmic game theory.