@inproceedings{667cbcbb56394ff6bf2b3640b34f5386,
title = "The tropical shadow-vertex algorithm solves mean payoff games in polynomial time on average",
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 (R ∪ \{-∞\}, 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{\"u}cker relations.",
author = "Xavier Allamigeon and Pascal Benchimol and St{\'e}phane Gaubert",
year = "2014",
month = jan,
day = "1",
doi = "10.1007/978-3-662-43948-7\_8",
language = "English",
isbn = "9783662439470",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
number = "PART 1",
pages = "89--100",
booktitle = "Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings",
edition = "PART 1",
note = "41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 ; Conference date: 08-07-2014 Through 11-07-2014",
}