The tropical shadow-vertex algorithm solves mean payoff games in polynomial time on average

Xavier Allamigeon 1, 2 Pascal Benchimol 1, 2 Stéphane Gaubert 1, 2
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
Abstract : We introduce an algorithm which solves mean payoff games in polynomial time on average, assuming the distribution of the games satisfies a flip invariance property on the set of actions associated with every state. The algorithm is a tropical analogue of the shadow-vertex simplex algorithm, which solves mean payoff games via linear feasibility problems over the tropical semiring (ℝ∪{−∞},max,+). The key ingredient in our approach is that the shadow-vertex pivoting rule can be transferred to tropical polyhedra, and that its computation reduces to optimal assignment problems through Plücker relations.
Type de document :
Communication dans un congrès
Javier Esparza; Pierre Fraigniaud; Thore Husfeldt; Elias Koutsoupias. ICALP 2014, Jul 2014, Copenhagen, France. Springer, Automata, Languages, and Programming, 8572, pp.12, 2014, 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I. 〈10.1007/978-3-662-43948-7_8〉
Liste complète des métadonnées
https://hal.inria.fr/hal-01096447
Contributeur : Xavier Allamigeon <>
Soumis le : mercredi 17 décembre 2014 - 15:09:31
Dernière modification le : jeudi 10 mai 2018 - 02:05:48

Lien texte intégral

arxiv

Identifiants

Collections

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

Citation

Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert. The tropical shadow-vertex algorithm solves mean payoff games in polynomial time on average. Javier Esparza; Pierre Fraigniaud; Thore Husfeldt; Elias Koutsoupias. ICALP 2014, Jul 2014, Copenhagen, France. Springer, Automata, Languages, and Programming, 8572, pp.12, 2014, 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I. 〈10.1007/978-3-662-43948-7_8〉. 〈hal-01096447〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

342

Contact


archive-ouverte@inria.fr