Evènement pour le groupe Séminaire Méthodes Formelles


Date 2018-06-05  11:00-12:00
TitreA 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. 
Lieu178 
OrateurLaure Daviaud 
Emailhttps://warwick.ac.uk/fac/sci/dcs/people/laure_daviaud/ 
UrlUniversity of Warwick 



Aucun document lié à cet événement.

Retour
Retour à l'index