Algorithmique à Garanties de Performance (Agape)

Projet du Pôle 2 Optimisation combinatoire, algorithmique

Le domaine de l’algorithmique à garanties de performance met en synergie de nombreuses compétences issues en grande partie de la Recherche Opérationnelle 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.

Le projet AGaPe développe quatre axe principaux :

  1. Approximation, domaine phare de l’activité des membres du projet depuis de nombreuses années. Le travail dans cet axe porte à la fois sur l’approximation polynomiale (qui inclue des approches plus récentes telles l’approximation multicritère, les problèmes labellisés et la robustesse) et l’approximation modérément exponentielle (domaine initié par les membres du projet) et paramétrée ;
  2. Résolution exacte et complexité ;
  3. Modèles d’optimisation pour des problèmes évolutifs (algorithmique online, réoptimisation et optimisation combinatoire probabiliste ;
  4. Jeux algorithmiques et optimisation combinatoire.