 |
HAL UPEC - UPEM Portal |  |
 |
Journal articles
Improved Pseudo-polynomial Bound for the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games
Abstract : In this work we offer an O(|V|² |E| W) pseudo-polynomial time deterministic algorithm for solving the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games. This improves by a factor log(|V| W) the best previously known pseudo-polynomial time upper bound due to Brim et al. The improvement hinges on a suitable characterization of values, and a description of optimal positional strategies, in terms of reweighted Energy Games and Small Energy-Progress Measures.
Cited literature [11 references]
https://hal-upec-upem.archives-ouvertes.fr/hal-01577457
Contributor : Admin Upem <>
Submitted on : Friday, August 25, 2017 - 5:38:23 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:07 PM
Contributor : Admin Upem <>
Submitted on : Friday, August 25, 2017 - 5:38:23 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:07 PM
File
1503.04426.pdf
Files produced by the author(s)