A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games

DOI10.1016/J.DAM.2006.04.029MaRDI QIDQ867862zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

cyclic gameergodic partitioniterative improvementcombinatorial linear programminglongest shortest pathmean payoff gameparity gamerandomized subexponential algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) 2-person games (91A05) Games involving graphs (91A43)

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

Cites work

• scientific article; zbMATH DE number 1670778 (Why is no real title available?)
• scientific article; zbMATH DE number 3542195 (Why is no real title available?)
• scientific article; zbMATH DE number 549853 (Why is no real title available?)
• scientific article; zbMATH DE number 1059247 (Why is no real title available?)
• scientific article; zbMATH DE number 1962853 (Why is no real title available?)
• A subexponential bound for linear programming
• A subexponential randomized algorithm for the simple stochastic game problem
• Combinatorial structure and randomized subexponential algorithms for infinite games
• Completely unimodal numberings of a simple polytope
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Extending Dijkstra’s Algorithm to Maximize the Shortest Path by Node-Wise Limited Arc Interdiction
• Extensions of two person zero sum games
• Introduction to algorithms
• Linear Programming Polytope and Algorithm for Mean Payoff Games
• Mean cost cyclical games
• Memoryless determinacy of parity and mean payoff games: a simple proof
• On Nonterminating Stochastic Games
• On model checking for the -calculus and its fragments
• Perspectives of System Informatics
• Positional strategies for mean payoff games
• The complexity of mean payoff games on graphs
• The complexity of stochastic games

Cited in

(52)

• scientific article; zbMATH DE number 7533361 (Why is no real title available?)
• Using strategy improvement to stay alive
• A superpolynomial lower bound for strategy iteration based on snare memorization
• On solving mean payoff games using pivoting algorithms
• Optimal strategies in weighted limit games
• Tropical linear-fractional programming and parametric mean payoff games
• Computation of weighted sums of rewards for concurrent MDPs
• scientific article; zbMATH DE number 5292473 (Why is no real title available?)
• Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
• Using strategy improvement to stay alive
• Tropical Fourier-Motzkin elimination, with an application to real-time verification
• The complexity of infinitely repeated alternating move games
• Improved complexity analysis of quasi-polynomial algorithms solving parity games
• 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
• An average polynomial algorithm for solving antagonistic games on graphs
• Parity games with weights
• Potential theory for mean payoff games
• The mu-calculus and Model Checking
• Tropicalizing the simplex algorithm
• Mathematical Foundations of Computer Science 2004
• The level set method for the two-sided max-plus eigenproblem
• An objective improvement approach to solving discounted payoff games
• Priority promotion with Parysian flair
• Incentive Stackelberg mean-payoff games
• On short paths interdiction problems: Total and node-wise limited interdiction
• The worst-case complexity of symmetric strategy improvement
• Faster algorithms for mean-payoff games
• Solving parity games in big steps
• Solving mean-payoff games via quasi dominions
• From Parity and Payoff Games to Linear Programming
• Tropical polyhedra are equivalent to mean payoff games
• Solving Parity Games in Big Steps
• A convex programming-based algorithm for mean payoff stochastic games with perfect information
• Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria
• 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
• Solving mean-payoff games via quasi dominions
• The complexity of all-switches strategy improvement
• Combinatorial simplex algorithms can solve mean payoff games
• Beyond value iteration for parity games: strategy iteration with universal trees
• 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
• An objective improvement approach to solving discounted payoff games
• Symmetric strategy improvement
• Fast algorithms for energy games in special cases

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)