Colloquium Polaris - Claire Mathieu
Nous vous donnons rendez-vous le jeudi 17 octobre dans l'amphi de l'Ircica de 14h à 15h30 pour un talk de Claire Mathieu dans le cadre du Colloquium Polaris . Elle nous expliquera : "The effectiveness of Local Search" .
- Date : 17/10/2019
- Lieu : Ircica, 50 avenue Halley, Parc scientifique de la Haute Borne, Villeneuve d'Ascq
- Intervenant(s) : Claire Mathieu
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.
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.