Publication details
Faster algorithms for mean
-payoff games
| Basic information | |
|---|---|
| Original title: | Faster algorithms for mean-payoff games |
| Authors: | Luboš Brim, Jakub Chaloupka, Laurent Doyen, Raffaella Gentilini, Jean-François Raskin |
| Further information | |
|---|---|
| Citation: | BRIM, Luboš - CHALOUPKA, Jakub - DOYEN, Laurent - GENTILINI, Raffaella - RASKIN, Jean-François. Faster algorithms for mean-payoff games. Formal Methods in System Design, Springer Netherlands, The Nederlands. ISSN 0925-9856, 2011, vol. 38, no. 2, pp. 97-118. |
| Original language: | English |
| Field: | Informatika |
| Type: | Article in Periodical |
| Keywords: | Mean payoff objectives; Algorithms and complexity upper bounds |
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.
Related projects:
- Highly Parallel and Distributed Computing Systems
- Verification and Analysis of Large-Scale Computer Systems
