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
Sergei Vorobyov, Henrik Björklund
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 (45)
- Title not available (Why is that?)
- A superpolynomial lower bound for strategy iteration based on snare memorization
- Incentive Stackelberg Mean-Payoff Games
- 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
- 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
- Cyclic games and linear programming
- On an algorithm for successive improvement of a strategy
- Abstract tropical linear programming
- Symmetric Strategy Improvement
- Looking at mean-payoff and total-payoff through windows
- A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions
- 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
- Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games
- The level set method for the two-sided max-plus eigenproblem
- Priority promotion with Parysian flair
- Title not available (Why is that?)
- On short paths interdiction problems: Total and node-wise limited interdiction
- On Solving Mean Payoff Games Using Pivoting Algorithms
- Solving Mean-Payoff Games via Quasi Dominions
- 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
- Title not available (Why is that?)
- Solving Parity Games in Big Steps
- Polynomial-time algorithms for energy games with special weight structures
- 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
- Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games
- Tropicalizing the Simplex Algorithm
- The Complexity of Infinitely Repeated Alternating Move 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
- Title not available (Why is that?)
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)
