Back to Search
Start Over
COMBINATORIAL SIMPLEX ALGORITHMS CAN SOLVE MEAN PAYOFF GAMES.
- Source :
- SIAM Journal on Optimization; 2014, Vol. 24 Issue 4, p2096-2117, 22p
- Publication Year :
- 2014
-
Abstract
- A combinatorial simplex algorithm is an instance of the simplex method in which the pivoting depends on certain 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. Mean payoff games are known to be in NP ⋂ 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 nondegenerate linear program over Hahn series. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10526234
- Volume :
- 24
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- SIAM Journal on Optimization
- Publication Type :
- Academic Journal
- Accession number :
- 101483978
- Full Text :
- https://doi.org/10.1137/140953800