Accueil/ expose
MOOC - Approximation Algorithms
mardi 01 décembre 2015

Loading the player...
Descriptif

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.

Voir le cours sur le site de Coursera

Auteur(s)
Claire Mathieu
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

Cliquer ICI pour fermer
Annexes
Téléchargements :
   - Télécharger la vidéo

Dernière mise à jour : 07/12/2015