Faster Algorithm for Mean-Payoff Games

CHALOUPKA, Jakub a Luboš BRIM. Faster Algorithm for Mean-Payoff Games. In Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09). Dagstuhl, Německo: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Německo, 2009, 9 s. ISBN 978-3-939897-15-6.

Základní údaje

Originální název

Faster Algorithm for Mean-Payoff Games

Název česky

Rychlejší algorimus pro mean-payoff hry

Autoři

CHALOUPKA, Jakub a Luboš BRIM

Vydání

Dagstuhl, Německo, Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09), 9 s. 2009

Nakladatel

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Německo

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Odkazy

URL

Kód RIV

RIV/00216224:14330/09:00029949

Organizační jednotka

Fakulta informatiky

ISBN

978-3-939897-15-6

Klíčová slova anglicky

mean-payoff games; randomized algorithms; complexity

Štítky

complexity, mean-payoff games, randomized algorithms

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

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