Faster Pseudo-Polynomial Algorithms for Mean-Payoff Games

Raffaella Gentilini
ULB
Friday, 27 November, 2009 (All day)
NO

We consider two-player games played on a weighted graph with mean-payoff objectives. We present a new pseudo-polynomial algorithm for solving such games, improving the best known worst-case complexity for pseudo-polynomial mean-payoff algorithms. Our solution relies on a simple fixpoint iteration to solve the log-space equivalent problem of deciding the winner of energy games.