Détail

Document sans titre

Séminaire du thème :

Programmation linéaire, convexité tropicale, et jeux répétés
Le 18 Juin 2014 à 14h00

Intervenant

Stéphane Gaubert
INRIA and CMAP, École Polytechnique, CNRS UMR 7641

E-mail : Stephane.Gaubert@inria.fr
Site : http://www.cmap.polytechnique.fr/~gaubert/

Lieu

LAAS-CNRS - Salle du Conseil
7 avenue du Colonel Roche
31077 TOULOUSE Cedex 4

Résumé

La géométrie tropicale permet de relier des questions non-résolues concernant la programmation linéaire et les jeux à somme nulle. La première concerne l'existence d'une règle de pivotage permettant de résoudre un programme linéaire par la méthode du simplexe avec un nombre de pivots polynômial en le nombre de variables et en le nombre de contraintes. La seconde concerne l'existence d'un algorithme polynômial pour les jeux déterministes répétés avec paiement moyen. Nous montrons qu'une solution positive à la première question résoudrait aussi la seconde, pourvu que la règle de pivotage satisfasse certaines conditions (règles combinatoires, et plus généralement semi-algébriques). L'approche tropicale, appliquée cette fois-ci aux méthodes de points intérieurs, permet aussi de construire des exemples de programmes linéaires classiques avec de grands coefficients pour lesquels le chemin central a une grande courbure totale. Il s'agit d'un travail commun avec Allamigeon, Benchimol, et Joswig, qui utilise un travail avec Akian et Guterman (équivalence entre programmation linéaire tropicale et jeux répétés).

Quelques Références.

  • M. Akian, S. Gaubert, A. Guterman, Tropical polyhedra are equivalent to mean payoff games, International Journal of Algebra and Computation, 22(01), 2012.
  • Tropicalizing th e Simplex Algorithm, 2013 arXiv:1308.0454
  • X. Allamigeon, P. Benchimol, S. Gaubert, M. Joswig, Combinatorial simplex algorithms can solve mean payoff games, 2013, arXiv:1309.5925
  • X. Allamigeon, P. Benchimol, S. Gaubert, M. Joswig, Long and winding central paths, arXiv:1405.4161





Retour

Export au format PDF Ajouter à mon calendrier
Export au format PDF Ajouter à mon calendrier