A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
From MaRDI portal
Publication:867862
DOI10.1016/J.DAM.2006.04.029zbMATH Open1176.68087OpenAlexW2114657710MaRDI QIDQ867862FDOQ867862
Authors: Henrik Björklund, Sergei Vorobyov 
Publication date: 19 February 2007
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2006.04.029
Recommendations
- Mathematical Foundations of Computer Science 2004
- The complexity of mean payoff games on graphs
- Potential theory for mean payoff games
- Combinatorial simplex algorithms can solve mean payoff games
- Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
cyclic gameergodic partitioniterative improvementcombinatorial linear programminglongest shortest pathmean payoff gameparity gamerandomized subexponential algorithm
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) 2-person games (91A05) Games involving graphs (91A43)
Cites Work
- The complexity of stochastic games
- The complexity of mean payoff games on graphs
- Introduction to algorithms
- A subexponential bound for linear programming
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Positional strategies for mean payoff games
- Cyclic games and an algorithm to find minimax cycle means in directed graphs
- On model checking for the \(\mu\)-calculus and its fragments
- A subexponential randomized algorithm for the simple stochastic game problem
- Mean cost cyclical games
- Memoryless determinacy of parity and mean payoff games: a simple proof
- Title not available (Why is that?)
- On Nonterminating Stochastic Games
- Extensions of two person zero sum games
- Title not available (Why is that?)
- Perspectives of System Informatics
- Extending Dijkstra’s Algorithm to Maximize the Shortest Path by Node-Wise Limited Arc Interdiction
- Combinatorial structure and randomized subexponential algorithms for infinite games
- Completely unimodal numberings of a simple polytope
- Linear Programming Polytope and Algorithm for Mean Payoff Games
Cited In (47)
- On solving mean payoff games using pivoting algorithms
- Optimal strategies in weighted limit games
- A superpolynomial lower bound for strategy iteration based on snare memorization
- Title not available (Why is that?)
- Computation of weighted sums of rewards for concurrent MDPs
- Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
- Tropical linear-fractional programming and parametric mean payoff games
- The complexity of infinitely repeated alternating move games
- Using strategy improvement to stay alive
- Improved complexity analysis of quasi-polynomial algorithms solving parity games
- Tropical Fourier-Motzkin elimination, with an application to real-time verification
- The complexity of all-switches strategy improvement
- Cyclic games and linear programming
- Synthesising strategy improvement and recursive algorithms for solving 2.5 player parity games
- On an algorithm for successive improvement of a strategy
- Abstract tropical linear programming
- Looking at mean-payoff and total-payoff through windows
- Parity games with weights
- An average polynomial algorithm for solving antagonistic games on graphs
- Potential theory for mean payoff games
- Mathematical Foundations of Computer Science 2004
- The mu-calculus and Model Checking
- Tropicalizing the simplex algorithm
- The level set method for the two-sided max-plus eigenproblem
- Priority promotion with Parysian flair
- Incentive Stackelberg mean-payoff games
- On short paths interdiction problems: Total and node-wise limited interdiction
- Solving mean-payoff games via quasi dominions
- Faster algorithms for mean-payoff games
- Solving parity games in big steps
- From Parity and Payoff Games to Linear Programming
- Tropical polyhedra are equivalent to mean payoff games
- Solving Parity Games in Big Steps
- Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria
- A convex programming-based algorithm for mean payoff stochastic games with perfect information
- A note on the approximation of mean-payoff games
- Parameterized Algorithms for Parity Games
- Solving mean-payoff games via quasi dominions
- Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games
- The complexity of all-switches strategy improvement
- Combinatorial simplex algorithms can solve mean payoff games
- Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games
- Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
- A faster deterministic exponential time algorithm for energy games and mean payoff games
- Symmetric strategy improvement
- Title not available (Why is that?)
- Using strategy improvement to stay alive
This page was built for publication: A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q867862)
