Skip to Main content Skip to Navigation
Conference papers

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
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.
Document type :
Conference papers
Complete list of metadata
https://hal.inria.fr/hal-01096447
Contributor : Xavier Allamigeon <>
Submitted on : Wednesday, December 17, 2014 - 3:09:31 PM
Last modification on : Thursday, March 5, 2020 - 6:34:12 PM

Links full text

arxiv

Identifiers

Collections

X | CNRS | INRIA | INSMI | X-CMAP | CMAP | TDS-MACS | 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. ICALP 2014, Jul 2014, Copenhagen, France. pp.12, ⟨10.1007/978-3-662-43948-7_8⟩. ⟨hal-01096447⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

507

 

Contact                    Legal Notice                    Personal Data