Faster algorithms for mean-payoff games

J 2011

Faster algorithms for mean-payoff games

BRIM, Luboš, Jakub CHALOUPKA, Laurent DOYEN, Raffaella GENTILINI, Jean-François RASKIN et. al.

Basic information

Original name

Faster algorithms for mean-payoff games

Authors

BRIM, Luboš (203 Czech Republic, guarantor, belonging to the institution), Jakub CHALOUPKA (203 Czech Republic, belonging to the institution), Laurent DOYEN (56 Belgium), Raffaella GENTILINI (380 Italy) and Jean-François RASKIN (56 Belgium)

Edition

Formal Methods in System Design, Springer Netherlands, 2011, 0925-9856

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Impact factor

Impact factor: 0.690

RIV identification code

RIV/00216224:14330/11:00050261

Organization unit

Faculty of Informatics

DOI

http://dx.doi.org/10.1007/s10703-010-0105-x

UT WoS

000288671700001

Keywords in English

Mean payoff objectives; Algorithms and complexity upper bounds

Abstract

V originále

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.

Links

GA201/09/1389, research and development project

Name: Verifikace a analýza velmi velkých počítačových systémů

Investor: Czech Science Foundation, Verification and Analysis of Large-Scale Computer Systems

MSM0021622419, plan (intention)

Name: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems

Citovat

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.

@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.

Detailed Information on Publication Record