讨论组:学生讲座
标题:Some New Results to the Simple Stochastic Games
演讲人: 戴德承 清华大学
时间: 2010-05-27 16:00-2010-05-27 17:00
地点:FIT1-222

内容:

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 \tileO(sqrt{ |V_R|! } ) time, where |V_R| is the number of RANDOM vertices and \tileO ignores polynomial terms. This algorithm is the fastest known algorithm when |V_R| = ω(log n) and |VR| = o( sqrt{min |Vmin|, |Vmax|}) and it works for general (non-stopping) simple stochastic games.




人物介绍: