Using strategy improvement to stay alive

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F12%3A00057380" target="_blank" >RIV/00216224:14330/12:00057380 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1142/S0129054112400291" target="_blank" >http://dx.doi.org/10.1142/S0129054112400291</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1142/S0129054112400291" target="_blank" >10.1142/S0129054112400291</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Using strategy improvement to stay alive

Popis výsledku v původním jazyce

We design a novel algorithm for solving Mean-Payoff Games (MPGs). Besides solving an MPG in the usual sense, our algorithm computes more information about the game, information that is important with respect to applications. The weights of the edges of an MPG can be thought of as a gained/consumed energy ? depending on the sign. For each vertex, our algorithm computes the minimum amount of initial energy that is sufficient for player Max to ensure that in a play starting from the vertex, the energy level never goes below zero. Our algorithm is not the first algorithm that computes the minimum sufficient initial energies, but according to our experimental study it is the fastest algorithm that computes them. The reason is that it utilizes the strategy improvement technique which is very efficient in practice.

Název v anglickém jazyce

Using strategy improvement to stay alive

Popis výsledku anglicky

We design a novel algorithm for solving Mean-Payoff Games (MPGs). Besides solving an MPG in the usual sense, our algorithm computes more information about the game, information that is important with respect to applications. The weights of the edges of an MPG can be thought of as a gained/consumed energy ? depending on the sign. For each vertex, our algorithm computes the minimum amount of initial energy that is sufficient for player Max to ensure that in a play starting from the vertex, the energy level never goes below zero. Our algorithm is not the first algorithm that computes the minimum sufficient initial energies, but according to our experimental study it is the fastest algorithm that computes them. The reason is that it utilizes the strategy improvement technique which is very efficient in practice.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2012

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

International Journal of Foundations of Computer Science

ISSN

0129-0541

e-ISSN

—

Svazek periodika

23

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

CZ - Česká republika

Počet stran výsledku

24

Strana od-do

585-608

Kód UT WoS článku

000304003000003

EID výsledku v databázi Scopus

—