How efficiently can you pack objects into a minimum number of boxes? How well can you cluster nodes so as to cheaply separate a network into components around a few centers? These are examples of NP-hard combinatorial optimization problems. It is most likely impossible to solve such problems efficiently, so our aim is to give an approximate solution that can be computed in polynomial time and that at the same time has provable guarantees on its cost relative to the optimum.
ENS / CNRS
Directrice de recherche / Professeure
Plus sur cet auteur
Voir la fiche de l'auteur
Institutions : Ecole normale supérieure-PSL
Cursus :
Claire Mathieu est depuis mai 2012, directrice de recherche au CNRS dans l'équipe Talgo et depuis septembre 2014, également professeur attaché à l'ENS. Récemment, elle s'est plus particulièrement attachée aux thématiques suivantes :
- les problèmes pour les graphes de planification
- les modèles de probabilité des réseaux sociaux
- les hiérarchies dans les relaxations de programmation semi-définie
- la tomographie des réseaux
- la programmation pour la minimisation de l'énergie
- les algorithmes en ligne
Prix et médailles:
Prix du Jeune Chercheur IBM / Élue membre junior de l'Institut Universitaire de France (IUF) / Prix INFORMS 2007 ICS
Dernière mise à jour : 07/12/2015
Tous droits réservés
@ 2011 ENS