Claire Mathieu - Local search for clustering type problems

12:00
Thursday
4
May
2017
  • Keynote Speech
Place: 
Organized by: 
L’équipe "Keynotes" du LIG
Speaker: 
Claire Mathieu, CNRS

Claire Mathieu does research on the design and analysis of algorithms, with a focus on approximation algorithms, particularly approximation schemes for NP-hard problems. A former student of Ecole normale supérieure, she received a PhD in Computer Science in 1988 at Paris-Sud University. She has held research and faculty positions at CNRS, Paris-Sud University, Ecole Polytechnique, and Brown University. She is currently a CNRS research director in the Computer Science department at École normale supérieure.

Réalisation technique : Antoine Orlandi | Tous droits réservés

Local search is a popular heuristic to find solutions to hard problems. How good are those solutions? There is a risk of getting stuck in a local optimum whose value is quite far from the optimal value. Here, we propose a broadened version of local search, where we enlarge the local neighborhood. Clustering problems aims to partition input data according to similarity. We will show that for several types of clustering problems, enlarged local search finds a nearly optimal solution. The key is to work in a space with good separability structure.