| Identifikační kód | RIV/00216224:14330/11:00050261 |
|---|
| Název v anglickém jazyce | Faster algorithms for mean-payoff games |
|---|
| Druh | J - Článek v odborném periodiku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2011 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 2 |
|---|
| Počet tvůrců celkem | 5 |
|---|
| Počet domácích tvůrců | 2 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Luboš Brim (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 6500773)
Jakub Chaloupka (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 5376327)
Laurent Doyen (státní příslušnost: BE - Belgické království)
Raffaella Gentilini (státní příslušnost: IT - Italská republika)
Jean-François Raskin (státní příslušnost: BE - Belgické království) |
|---|
| Popis výsledku v anglickém jazyce | 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. |
|---|
| Klíčová slova oddělená středníkem | Mean payoff objectives; Algorithms and complexity upper bounds |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.1007/s10703-010-0105-x |
|---|