scientific article; zbMATH DE number 6970803

DOI10.23638/LMCS-14(4:9)2018zbMath1402.68089arXiv1507.04500MaRDI QIDQ4553289

Rahul Savani, John Fearnley

Publication date: 2 November 2018

Full work available at URL: https://arxiv.org/abs/1507.04500

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

parity gamesPSPACE-completenessmean-payoff gamessimple stochastic gamesdiscounted gamesunique sink orientationsstrategy improvement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Unique sink orientations of grids
• How easy is local search?
• The complexity of stochastic games
• On the complexity of the parity argument and other inefficient proofs of existence
• The complexity of mean payoff games on graphs
• Mathematical problems for the next century
• Automata, logics, and infinite games. A guide to current research
• A subexponential randomized algorithm for the simple stochastic game problem
• A subexponential bound for linear programming
• The Complexity of the Simplex Method
• The Complexity of Recognizing Unique Sink Orientations
• Non-oblivious Strategy Improvement
• An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms
• Linear Complementarity Algorithms for Infinite Games
• A Simple P-Matrix Linear Complementarity Problem for Discounted Games
• An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
• A deterministic subexponential algorithm for solving parity games
• Linear programming and unique sink orientations
• Exponential Lower Bounds for Policy Iteration
• Jumping Doesn’t Help in Abstract Cubes
• The Complexity of All-switches Strategy Improvement
• The Simplex Algorithm Is NP-Mighty
• Deciding parity games in quasipolynomial time
• Improved upper bounds for Random-Edge and Random-Jump on abstract cubes
• On Simplex Pivoting Rules and Complexity Theory
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
• The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions
• On Nonterminating Stochastic Games

This page was built for publication: