A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
From MaRDI portal
Publication:867862
DOI10.1016/j.dam.2006.04.029zbMath1176.68087OpenAlexW2114657710MaRDI QIDQ867862
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
cyclic gameergodic partitioniterative improvementcombinatorial linear programminglongest shortest pathmean payoff gameparity gamerandomized subexponential algorithm
Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) 2-person games (91A05) Games involving graphs (91A43) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES, Symmetric Strategy Improvement, Tropicalizing the Simplex Algorithm, The mu-calculus and Model Checking, USING STRATEGY IMPROVEMENT TO STAY ALIVE, From Parity and Payoff Games to Linear Programming, An average polynomial algorithm for solving antagonistic games on graphs, Solving parity games in big steps, The level set method for the two-sided max-plus eigenproblem, Tropical Fourier–Motzkin elimination, with an application to real-time verification, Incentive Stackelberg Mean-Payoff Games, The Complexity of Infinitely Repeated Alternating Move Games, Unnamed Item, Parameterized Algorithms for Parity Games, A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions, A convex programming-based algorithm for mean payoff stochastic games with perfect information, Abstract tropical linear programming, Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria, Improved complexity analysis of quasi-polynomial algorithms solving parity games, Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games, Solving mean-payoff games via quasi dominions, Tropical linear-fractional programming and parametric mean payoff games, Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games, Unnamed Item, A superpolynomial lower bound for strategy iteration based on snare memorization, A note on the approximation of mean-payoff games, On short paths interdiction problems: Total and node-wise limited interdiction, Computation of weighted sums of rewards for concurrent MDPs, Polynomial-time algorithms for energy games with special weight structures, Cyclic games and linear programming, Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games, Solving Mean-Payoff Games via Quasi Dominions, Faster algorithms for mean-payoff games, Unnamed Item, Unnamed Item, On Solving Mean Payoff Games Using Pivoting Algorithms, Solving Parity Games in Big Steps, Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time, Looking at mean-payoff and total-payoff through windows
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Combinatorial structure and randomized subexponential algorithms for infinite games
- Completely unimodal numberings of a simple polytope
- Positional strategies for mean payoff games
- The complexity of stochastic games
- Extensions of two person zero sum games
- The complexity of mean payoff games on graphs
- Memoryless determinacy of parity and mean payoff games: a simple proof
- A subexponential randomized algorithm for the simple stochastic game problem
- A subexponential bound for linear programming
- Mean Cost Cyclical Games
- Extending Dijkstra’s Algorithm to Maximize the Shortest Path by Node-Wise Limited Arc Interdiction
- Cyclic games and an algorithm to find minimax cycle means in directed graphs
- Linear Programming Polytope and Algorithm for Mean Payoff Games
- On Nonterminating Stochastic Games
- Perspectives of System Informatics
- On model checking for the \(\mu\)-calculus and its fragments
