Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
From MaRDI portal
Publication:3012799
DOI10.1007/978-3-642-22006-7_13zbMath1332.68064OpenAlexW1509251183MaRDI QIDQ3012799
Kazuhisa Makino, Endre Boros, Bodo Manthey, Mahmoud Fouz, Khaled M. Elbassioni, Vladimir A. Gurvich
Publication date: 6 July 2011
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_13
Analysis of algorithms and problem complexity (68Q25) Stochastic games, stochastic differential games (91A15) Approximation algorithms (68W25)
Related Items
Incentive Stackelberg Mean-Payoff Games ⋮ Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design ⋮ A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions ⋮ A quantization framework for smoothed analysis of Euclidean optimization problems ⋮ A note on the approximation of mean-payoff games ⋮ Polynomial-time algorithms for energy games with special weight structures ⋮ Approximation schemes for stochastic mean payoff games with perfect information and few random positions ⋮ Approximating the minimum cycle mean ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Cyclical games with prohibitions
- Cyclic games and linear programming
- Matching is as easy as matrix inversion
- The complexity of mean payoff games on graphs
- Cyclic games and an algorithm to find minimax cycle means in directed graphs
- A Pumping Algorithm for Ergodic Stochastic Mean Payoff Games with Perfect Information
- Smoothed analysis of algorithms
- The Complexity of Solving Stochastic Games on Graphs
- Typical Properties of Winners and Losers [0.2ex in Discrete Optimization]
- On Nonterminating Stochastic Games
- Stochastic Games with Perfect Information and Time Average Payoff
This page was built for publication: Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
