2006.09.06 | Gerth Stølting Brodal

Title: Improved Algorithms for Discounted Payoff Games

Abstract:

This talk is devoted to the design and analysis of combinatorial
algorithms for solving one-player versions of several prominent
infinite duration games pertinent to automated verification of
computerized systems.

We present the first two strongly polynomial algorithms for solving
one-player discounted payoff games, running in time
$O(mn2)$ and $O(mn2 \\log m)$, where the latter
algorithm allows edges to have different discounting factors. As
applications, we are able to improve the best previously known
strongly subexponential algorithms for solving two-player discounted
payoff games and the ergodic partitioning problem for mean payoff
games.