Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games
From MaRDI portal
Publication:5089201
DOI10.4230/LIPICS.MFCS.2020.34OpenAlexW3043364318MaRDI QIDQ5089201
Nathanaël Fijalkow, Paweł Gawrychowski, Pierre Ohlmann
Publication date: 18 July 2022
Full work available at URL: https://hal-cnrs.archives-ouvertes.fr/hal-03800510
Related Items (3)
The Theory of Universal Graphs for Infinite Duration Games ⋮ New algorithms for combinations of objectives using separating automata ⋮ The GKK algorithm is the fastest over simple mean-payoff games
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
- Faster algorithms for mean-payoff games
- An application of simultaneous diophantine approximation in combinatorial optimization
- Positional strategies for mean payoff games
- Infinite games on finitely coloured graphs with applications to automata on infinite trees
- The complexity of mean payoff games on graphs
- Linear programming, the simplex algorithm and simple polytopes
- Mathematical problems for the next century
- A subexponential bound for linear programming
- Universal graphs and good for games automata: new tools for infinite duration games
- Cyclic games and an algorithm to find minimax cycle means in directed graphs
- Implicat Representation of Graphs
- Deciding parity games in quasipolynomial time
- Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
- A pseudo-quasi-polynomial algorithm for mean-payoff parity games
- A modal μ perspective on solving parity games in quasi-polynomial time
- Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
- Combinatorial Simplex Algorithms Can Solve Mean Payoff Games
- Optimal Distance Labeling Schemes for Trees
This page was built for publication: Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games
