Bruno Escoffier : Algorithmes approchés, une frontière sur les compromis temps/qualité

Bruno Escoffier
UPMC, LIP6, Paris

La conception d'algorithmes approchés pour la résolution de problèmes difficiles montre l'existence de compromis algorithmiques possibles entre qualité de la solution calculée et complexité en temps. En grande partie focalisée sur les algorithmes de complexité polynomiale, un des développements récents de la thématique de l'approximation concerne les compromis atteignables par des algorithmes de complexité plus élevée.
Nous retracerons dans cet exposé certaines avancées importantes de la théorie de l'approximation polynomiale, puis présenterons certains résultats plus récents concernant des complexités non polynomiales.

Bruno Escoffier a reçu son Doctorat en 2005 et son Habilitation à Diriger des Recherches en 2012, tous deux en Informatique et de l'Université Paris-Dauphine, établissement où il a été Maître de Conférences entre 2006 et 2013. Depuis 2013 il est Professeur à l'UPMC et membre de l'équipe "Recherche Opérationnelle" du laboratoire LIP6. Il travaille sur la conception d'algorithmes approchés, exponentiels et paramétrés pour la résolution de problèmes d'optimisation difficiles. Il est l'auteur d'une trentaine d'articles dans des revues internationales, et a reçu la médaille de bronze du CNRS en 2011.