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.
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 2017, 77 (4), pp.995-1021. 〈10.1007/s00453-016-0123-1〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal-upec-upem.archives-ouvertes.fr/hal-01577457
Contributeur : Admin Upem <>
Soumis le : vendredi 25 août 2017 - 17:38:23
Dernière modification le : jeudi 5 juillet 2018 - 14:45:41

Fichier

1503.04426.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Carlo Comin, Romeo Rizzi. Improved Pseudo-polynomial Bound for the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games. Algorithmica, Springer Verlag, 2017, 77 (4), pp.995-1021. 〈10.1007/s00453-016-0123-1〉. 〈hal-01577457〉

Partager

Métriques

Consultations de la notice

104

Téléchargements de fichiers

49