A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
- 作者：Henrik Bjö ; rklund ; Sergei Vorobyov
- 关键词：Mean payoff game ; Cyclic game ; Parity game ; Ergodic partition ; Combinatorial linear programming ; Longest shortest parth ; Iterative improvement ; Randomized subexponential algorithm
- 刊名：Discrete Applied Mathematics
- 出版年：2007
- 期刊代码：46_0166218x
- 类别：cp
- 出版时间：15 January 2007
- 卷：155
- 期：2
- 页码：210-229
- 文件大小：286 K
摘要
We suggest the first strongly subexponential and purely combinatorial algorithm for solving the mean payoff games problem. It is based on iteratively improving the longest shortest distances to a sink in a possibly cyclic directed graph.
We identify a new “controlled” version of the shortest paths problem. By selecting exactly one outgoing edge in each of the controlled vertices we want to make the shortest distances from all vertices to the unique sink as long as possible. The decision version of the problem (whether the shortest distance from a given vertex can be made bigger than a given bound?) belongs to the complexity class 2464cbb0140f" title="Click to view the MathML source">NP∩CONP, which is simultaneously pseudopolynomial (W is the maximal absolute edge weight) and subexponential in the number of vertices n. All previous algorithms for mean payoff games were either exponential or pseudopolynomial (which is purely exponential for exponentially large edge weights).