Another sub-exponential algorithm for the simple stochastic game

DOI10.1007/s00453-010-9413-1zbMath1233.91027OpenAlexW2009945194MaRDI QIDQ652540

Decheng Dai, Rong Ge

Publication date: 14 December 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9413-1

zbMATH Keywords

subexponential algorithmsimple stochastic game

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Stochastic games, stochastic differential games (91A15) Randomized algorithms (68W20)

Related Items (4)

A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions ⋮ Unnamed Item ⋮ Approximation schemes for stochastic mean payoff games with perfect information and few random positions ⋮ Comparison of algorithms for simple stochastic games

Cites Work

• The complexity of stochastic games
• A subexponential randomized algorithm for the simple stochastic game problem
• Solving Simple Stochastic Games
• Stochastic Games
• Unnamed Item
• Unnamed Item

This page was built for publication: Another sub-exponential algorithm for the simple stochastic game