caa a22 4500 445805390 CHVBK 20180317145155.0 cr unu---uuuuu 170323e20111201xx s 000 0 eng 10.1007/s00453-010-9413-1 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9413-1 Another Sub-exponential Algorithm fortheSimple Stochastic Game [Elektronische Daten] [Decheng Dai, Rong Ge] 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 $\tilde{O}(\sqrt{|V_{\mathrm{R}}|!})$ time, where |V R| is the number of RANDOM vertices and $\tilde{O}$ ignores polynomial terms. This algorithm is the fastest known algorithm when |V R|=ω(log n) and $|V_{\mathrm{R}}|=o(\sqrt{\min{|V_{\min}|,|V_{\max}|}})$ and it works for general (non-stopping) simple stochastic games. Springer Science+Business Media, LLC, 2010 Simple stochastic game nationallicence Subexponential algorithm nationallicence Dai Decheng Tsinghua University, Beijing, China aut Ge Rong Princeton University, Princeton, USA aut Algorithmica Springer-Verlag 61/4(2011-12-01), 1092-1104 0178-4617 61:4<1092 2011 61 453 https://doi.org/10.1007/s00453-010-9413-1 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9413-1 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Dai Decheng Tsinghua University, Beijing, China aut NATIONALLICENCE 700 1- Ge Rong Princeton University, Princeton, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/4(2011-12-01), 1092-1104 0178-4617 61:4<1092 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer