The GKK algorithm is the fastest over simple mean-payoff games

DOI10.1007/978-3-031-09574-0_17OpenAlexW3206569936MaRDI QIDQ2097231

Pierre Ohlmann

Publication date: 11 November 2022

Full work available at URL: https://arxiv.org/abs/2110.04533

zbMATH Keywords

mean-payoff gamespseudopolynomialsymmetric algorithmGKK algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
• Faster algorithms for mean-payoff games
• Combinatorial structure and randomized subexponential algorithms for infinite games
• Positional strategies for mean payoff games
• Borel determinacy
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• The complexity of mean payoff games on graphs
• Mean Cost Cyclical Games
• Maximum-Minimum Sätze über Graphen
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Infinite Runs in Weighted Timed Automata with Energy Constraints
• Deciding parity games in quasipolynomial time
• Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games

This page was built for publication: The GKK algorithm is the fastest over simple mean-payoff games