文章基本信息

标题：A Faster Deterministic Exponential Time Algorithm for Energy Games and Mean Payoff Games
本地全文：下载
作者：Dani Dorfman ; Haim Kaplan ; Uri Zwick 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：132
页码：1-14
DOI：10.4230/LIPIcs.ICALP.2019.114
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We present an improved exponential time algorithm for Energy Games, and hence also for Mean Payoff Games. The running time of the new algorithm is O (min(m n W, m n 2^{n/2} log W)), where n is the number of vertices, m is the number of edges, and when the edge weights are integers of absolute value at most W. For small values of W, the algorithm matches the performance of the pseudopolynomial time algorithm of Brim et al. on which it is based. For W >= n2^{n/2}, the new algorithm is faster than the algorithm of Brim et al. and is currently the fastest deterministic algorithm for Energy Games and Mean Payoff Games. The new algorithm is obtained by introducing a technique of forecasting repetitive actions performed by the algorithm of Brim et al., along with the use of an edge-weight scaling technique.
关键词：Energy Games; Mean Payoff Games; Scaling