D 2009

Faster Algorithm for Mean-Payoff Games

CHALOUPKA, Jakub a Luboš BRIM

Základní údaje

Originální název

Faster Algorithm for Mean-Payoff Games

Název česky

Rychlejší algorimus pro mean-payoff hry

Autoři

Vydání

Brno, MEMICS 2009, od s. 45-53, 9 s. 2009

Nakladatel

NOVPRESS s.r.o.

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Česká republika

Utajení

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

Kód RIV

RIV/00216224:14330/09:00029686

Organizační jednotka

Fakulta informatiky

ISBN

978-80-87342-04-6

Klíčová slova anglicky

mean-payoff games; randomized algorithms; complexity

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 16. 12. 2009 14:14, RNDr. Jakub Chaloupka, Ph.D.

Anotace

ORIG CZ

V originále

We study some existing techniques for solving mean-payoff games (MPGs), improve them, and design a randomized algorithm for solving MPGs with currently the best expected complexity.

Česky

Podíváme se na některé existující techniky pro řešení mean-payoff her (MPGs), vylepšíme je a navrhneme náhodnostní algoritmus pro řešení MPGs se zatím nejlepší časovou složitostí.

Návaznosti

GA201/09/1389, projekt VaV
Název: Verifikace a analýza velmi velkých počítačových systémů
Investor: Grantová agentura ČR, Verifikace a analýza velmi velkých počítačových systémů
MSM0021622419, záměr
Název: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy