Evènement pour le groupe Séminaire Méthodes Formelles
|Date|| 2018-06-05 11:00-12:00|
|Titre||A pseudo-quasi-polynomial algorithm for mean-payoff parity games |
|Résumé||In a mean-payoff parity game, one of the two players aims both to achieve a qualitative parity objective and to minimize a quantitative long-term average of payoffs (aka. mean payoff). The game is zerosum and hence the aim of the other player is to either foil the parity objective or to maximize the mean payoff.
I will present a pseudo-quasi-polynomial algorithm for solving mean-payoff parity games. All algorithms for the problem that have been developed for over a decade have a pseudo-polynomial and an exponential factors in their running times; in the running time of our algorithm the latter is replaced with a quasi-polynomial one. |
|Orateur||Laure Daviaud |
|Url||University of Warwick |
Aucun document lié à cet événement.RetourRetour à l'index