Conférence de Stéphane Gaubert dans le cadre du séminaire général d'informatique.
Une question aussi ancienne que la programmation linéaire consiste à trouver une règle de pivotage pour l'algorithme du simplexe conduisant à un nombre polynomial d'opérations.
Une autre question consiste à trouver un algorithme résolvant en temps polynomial un jeu répété déterministe dont la valeur est définie comme un paiement moyen par unité de temps. Sans résoudre aucune de ces deux questions, nous montrons qu'une réponse positive à la première entraînerait une réponse positive à la seconde, pourvu que la règle de pivotage satisfasse certaines conditions.
La preuve de ce résultat fait appel à la convexité tropicale et nous servira de prétexte à faire une introduction à celle-ci.
Cet exposé est basé sur un travail avec Akian et Guterman (arXiv:0912.2462, IJAC 2012) ainsi que sur un travail avec Allamigeon, Benchimol, et Joswig arXiv:1308.0454, arXiv:1309.5925)
Catégories: Séminaire général du département d'informatique
Mot-clés : algèbre, programmation, algorithme, polynomial
Voir aussi
|
|
Cursus :
Stéphane Gaubert est professeur au département de mathématiques appliquées à l'École polytechnique.
Cliquer ICI pour fermerDernière mise à jour : 11/02/2021
Tous droits réservés
@ 2011 ENS