Faster algorithms for mean-payoff games
Faster algorithms for mean-payoff games
复制标题
DOI：
10.1007/s10703-010-0105-x
复制
发表时间：
2011-04-01
影响因子：
0.8
通讯作者：
Raskin, J. F.
中科院分区：
文献类型：
--
作者：
Brim, L.;Chaloupka, J.;Raskin, J. F.
在本文中，我们研究的定量模型，在嵌入式系统建模的应用程序的动机的算法问题。我们考虑两个玩家的游戏在一个加权图的平均支付目标和能量约束。我们提出了一个新的伪多项式算法来解决这样的游戏，提高了最好的已知的最坏情况下的伪多项式平均支付算法的复杂性。我们的算法也可以与Andersson和Vorobyov的过程相结合，以获得一个随机算法，目前最好的预期时间复杂度。所提出的解决方案依赖于一个简单的不动点迭代来解决对数空间等价的问题，决定能源游戏的赢家。我们的结果还意味着能量博弈和平均收益博弈可以在伪多项式时间内归结为安全博弈。
In this paper, we study algorithmic problems for quantitative models that are motivated by the applications in modeling embedded systems. We consider two-player games played on a weighted graph with mean-payoff objective and with energy constraints. We present a new pseudopolynomial algorithm for solving such games, improving the best known worst-case complexity for pseudopolynomial mean-payoff algorithms. Our algorithm can also be combined with the procedure by Andersson and Vorobyov to obtain a randomized algorithm with currently the best expected time complexity. The proposed solution relies on a simple fixpoint iteration to solve the log-space equivalent problem of deciding the winner of energy games. Our results imply also that energy games and mean-payoff games can be reduced to safety games in pseudopolynomial time.