Algorithmique à Garantie de Performance, Complexité Paramétrée, Schéma d’Approximation, Complexité Faiblement Exponentielle, Stochastique versus Plus Mauvais Cas, Algorithmique on-line, Ré-optimisation.
C’est à l’obtention des réponses à des questions de complexité et d’approximation pour tous les problèmes d’optimisation et de décision considérés dans les autres axes du GDR que s’intéresse l’axe CAGDO. Les recherches menées dans l’axe CAGDO se déclinent ainsi selon les quatre thèmes suivants : Résolution exacte, complexité paramétrée et algorithmes exponentiels, Approximation polynomiale, modérément exponentielle, sous-exponentielle et paramétrée, Complexité et approximation des problèmes d’optimisation et de décision dynamiques et/ou incertains, Propriétés structurelles des graphes pour l’optimisation et la décision.
