We study the algorithm of Gurvich, Khachyian and Karzanov (GKK algorithm) when it is ran over mean-payoff games with no simple cycle of weight zero. We propose a new symmetric analysis, lowering the $O(n^2 N)$ upper-bound of Pisaruk on the number of iterations down to $N + Ep + Em$, which is smaller than $nN$, where $n$ is the number of vertices, $N$ is the largest absolute value of a weight, and $Ep$ and $Em$ are respectively the largest finite energy and dual-energy values of the game. Since each iteration is computed in $O(m)$, this improves on the state of the art pseudopolynomial $O(mnN)$ runtime bound of Brim, Chaloupka, Doyen, Gentilini and Raskin, by taking into account the structure of the game graph. We complement our result by showing that the analysis of Dorfman, Kaplan and Zwick also applies to the GKK algorithm, which is thus also subject to the state of the art combinatorial runtime bound of $O(m 2^{n/2})$.

翻译：我们研究Gurvich、Khachyian和Karzanov(GKK算法)的算法,当它被运行在没有简单重量周期零的负负负游戏上时,我们建议进行新的对称分析,将Pisaruk对迭代数量上调降至N+Ep+Em美元,这个数额小于美元,即脊椎数为美元,美元是重量的最大绝对值,Epan美元和Em$分别为游戏中最大的有限能量和双重能量值。由于每次迭代用美元计算,考虑到游戏图的结构,Pisaruk对Brim、Chaloupka、Doyen、Gentilini和Raskin的运行时间约束状态有了改善,我们通过显示Dorfman、Caplan和Zwick$的分析也适用于GKKR2的运行状态,因此,GKKKR2的运行时值也是对GKKA的组合。