Historique

Le groupe a été créé au début des années 2000 et a fonctionné de manière régulière jusqu'en 2008. Il a continué de 2009 à 2013 sous la forme d'un projet ANR TODO (Time vs. Optimality in Discrete Optimization) impliquant les équipes fondatrices. En 2012-2013 dans le cadre d'une initiative thématique du GDR RO autour de la « Réoptimisation », la nécessité de refaire vivre le groupe en l'élargissant à d'autres chercheurs est devenue manifeste.

Objectifs Scientifiques

L'objectif du groupe « Algorithmique à Garanties de Performance » est d'étudier la résolution des problèmes difficiles par des algorithmes offrant des garanties de performance soit sur la qualité des solutions calculées, soit sur leurs temps d'exécution, soit sur la quantité de mémoire utilisée, ... Le domaine de l'algorithmique à garanties de performance met en synergie de nombreuses compétences issues en grande partie de la longue tradition scientifique de l'Optimisation Combinatoire et de l'Informatique Théorique : l'algorithmique, la théorie de la complexité, la programmation mathématique, les mathématiques discrètes et la combinatoire. Comme domaine scientifique, l'algorithmique à garanties de performance puise dans la Recherche Opérationnelle et l'Informatique Théorique son inspiration, sa problématique et ses motivations, et rend à ces disciplines de nouveaux concepts et de puissants outils d'analyse et de résolution.

Les thématiques du projet AGaPe se déclinent en 4 axes principaux :

  • Approximation polynomiale, modérément exponentielle, sous-exponentielle et paramétrée
  • Algorithmique sur des instances évolutives : algorithmique on-line, ré-optimisation, optimisation combinatoire probabiliste
  • Résolution exacte et paramétrée avec des bornes supérieures sur la complexité au pire des cas
  • Jeux algorithmiques et optimisation combinatoire