A faster deterministic exponential time algorithm for energy games and mean payoff games

DOI10.4230/LIPICS.ICALP.2019.114MaRDI QIDQ5091276zbMATH OpenFDO

Authors Dani Dorfman, Haim Kaplan, Uri Zwick

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2019.114

zbMATH Keywords

energy gamesMean Payoff Gamesscaling

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• Faster algorithms for mean-payoff games
• Mathematical Foundations of Computer Science 2004
• Potential theory for mean payoff games

Cites work

• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• A modal \(\mu\) perspective on solving parity games in quasi-polynomial time
• A subexponential bound for linear programming
• A subexponential randomized algorithm for the simple stochastic game problem
• An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
• Beyond the flow decomposition barrier
• Combinatorial structure and randomized subexponential algorithms for infinite games
• Deciding parity games in quasipolynomial time
• Faster algorithms for mean-payoff games
• Faster scaling algorithms for general graph matching problems
• Infinite Runs in Weighted Timed Automata with Energy Constraints
• Linear programming, the simplex algorithm and simple polytopes
• Positional strategies for mean payoff games
• Scaling Algorithms for the Shortest Paths Problem
• Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
• Succinct progress measures for solving parity games
• The complexity of mean payoff games on graphs

Cited in

(16)

• The GKK algorithm is the fastest over simple mean-payoff games
• Abstract tropical linear programming
• Using strategy improvement to stay alive
• Potential theory for mean payoff games
• Fixed-dimensional energy games are in pseudo-polynomial time
• The Theory of Universal Graphs for Infinite Duration Games
• Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games
• Using strategy improvement to stay alive
• Mathematical Foundations of Computer Science 2004
• Faster algorithms for mean-payoff games
• Solving mean-payoff games via quasi dominions
• Efficient Algorithms for Omega-Regular Energy Games
• The worst-case complexity of symmetric strategy improvement
• Fair quantitative games
• Fast algorithms for energy games in special cases
• Deterministic sub-exponential algorithm for discounted-sum games with unary weights

This page was built for publication: A faster deterministic exponential time algorithm for energy games and mean payoff games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091276)