Publications [#302363] of Rong Ge

Papers Published

1. Dai, D; Ge, R, Another sub-exponential algorithm for the simple stochastic game, Algorithmica New York, vol. 61 no. 4 (December, 2011), pp. 1092-1104, Springer Nature, ISSN 0178-4617 [doi]
   (last updated on 2026/01/16)

   Abstract:
   We study the problem of solving simple stochastic games, and give both an interesting new algorithm and a hardness result. We show a reduction from fine approximation of simple stochastic games to coarse approximation of a polynomial sized game, which can be viewed as an evidence showing the hardness to approximate the value of simple stochastic games. We also present a randomized algorithm that runs in Õ(√|V R|!) time, where |V R| is the number of RANDOM vertices and Õ ignores polynomial terms. This algorithm is the fastest known algorithm when |V R|= ω(logn) and |V R|=o(√min|V min|,|V max|) and it works for general (non-stopping) simple stochastic games. © 2010 Springer Science+Business Media, LLC.