Combinatorial Simplex Algorithms Can Solve Mean Payoff Games

Xavier Allamigeon 1, 2 Pascal Benchimol 1, 2 Stephane Gaubert 1, 2 Michael Joswig 3
1 CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique
2 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
3 TUB - Technische Universität Berlin
Abstract : A combinatorial simplex algorithm is an instance of the simplex method in which the pivoting depends on combinatorial data only. We show that any algorithm of this kind admits a tropical analogue which can be used to solve mean payoff games. Moreover, any combinatorial simplex algorithm with a strongly polynomial complexity (the existence of such an algorithm is open) would provide in this way a strongly polynomial algorithm solving mean payoff games (all the arithmetic operations being performed on data polynomially bounded in the size of the input, in particular). Mean payoff games are known to be in NP and co-NP; whether they can be solved in polynomial time is an open problem. Our algorithm relies on a tropical implementation of the simplex method over a real closed field of Hahn series. One of the key ingredients is a new scheme for symbolic perturbation which allows us to lift an arbitrary mean payoff game instance into a non-degenerate linear program over Hahn series.
Type de document :
Communication dans un congrès
The 21st International Symposium on Mathematical Theory of Networks and Systems (MTNS 2014), Jul 2014, Groningen, Netherlands. 〈https://fwn06.housing.rug.nl/mtns2014/〉
Liste complète des métadonnées
https://hal.inria.fr/hal-01097727
Contributeur : Pascal Benchimol <>
Soumis le : dimanche 21 décembre 2014 - 16:43:01
Dernière modification le : jeudi 10 mai 2018 - 02:04:27

Identifiants

  • HAL Id : hal-01097727, version 1

Collections

X | INRIA | INSMI | X-CMAP | CMAP | TDS-MACS | PARISTECH | X-DEP-MATHA

Citation

Xavier Allamigeon, Pascal Benchimol, Stephane Gaubert, Michael Joswig. Combinatorial Simplex Algorithms Can Solve Mean Payoff Games. The 21st International Symposium on Mathematical Theory of Networks and Systems (MTNS 2014), Jul 2014, Groningen, Netherlands. 〈https://fwn06.housing.rug.nl/mtns2014/〉. 〈hal-01097727〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

319

Contact


archive-ouverte@inria.fr