| BRIM, Luboš, Jakub CHALOUPKA, Laurent DOYEN, Raffaella GENTILINI and Jean-François RASKIN. Faster algorithms for mean-payoff games. Formal Methods in System Design. Springer Netherlands, 2011, vol. 38, No 2, p. 97-118. ISSN 0925-9856. Available from: https://dx.doi.org/10.1007/s10703-010-0105-x. |
Other formats:
BibTeX
LaTeX
RIS
@article{963533,
author = {Brim, Luboš and Chaloupka, Jakub and Doyen, Laurent and Gentilini, Raffaella and Raskin, JeanandFrançois},
article_number = {2},
doi = {http://dx.doi.org/10.1007/s10703-010-0105-x},
keywords = {Mean payoff objectives; Algorithms and complexity upper bounds},
language = {eng},
issn = {0925-9856},
journal = {Formal Methods in System Design},
title = {Faster algorithms for mean-payoff games},
volume = {38},
year = {2011}
}
TY - JOUR
ID - 963533
AU - Brim, Luboš - Chaloupka, Jakub - Doyen, Laurent - Gentilini, Raffaella - Raskin, Jean-François
PY - 2011
TI - Faster algorithms for mean-payoff games
JF - Formal Methods in System Design
VL - 38
IS - 2
SP - 97-118
EP - 97-118
PB - Springer Netherlands
SN - 09259856
KW - Mean payoff objectives
KW - Algorithms and complexity upper bounds
N2 - In this paper, we study algorithmic problems for quantitative models that are motivated by the applications in modeling embedded systems. We consider two-player games played on a weighted graph with mean-payoff objective and with energy constraints. We present a new pseudopolynomial algorithm for solving such games, improving the best known worst-case complexity for pseudopolynomial mean-payoff algorithms. Our algorithm can also be combined with the procedure by Andersson and Vorobyov to obtain a randomized algorithm with currently the best expected time complexity. The proposed solution relies on a simple fixpoint iteration to solve the log-space equivalent problem of deciding the winner of energy games. Our results imply also that energy games and mean-payoff games can be reduced to safety games in pseudopolynomial time.
ER -
BRIM, Luboš, Jakub CHALOUPKA, Laurent DOYEN, Raffaella GENTILINI and Jean-Fran$\backslash$c cois RASKIN. Faster algorithms for mean-payoff games. \textit{Formal Methods in System Design}. Springer Netherlands, 2011, vol.~38, No~2, p.~97-118. ISSN~0925-9856. Available from: https://dx.doi.org/10.1007/s10703-010-0105-x.
|
