Faster Algorithm for Mean-Payoff Games

CHALOUPKA, Jakub a Luboš BRIM. Faster Algorithm for Mean-Payoff Games. In MEMICS 2009. Brno: NOVPRESS s.r.o., 2009, s. 45-53. ISBN 978-80-87342-04-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 (203 Česká republika) a Luboš BRIM (203 Česká republika, garant).
• Vydání: Brno, MEMICS 2009, od s. 45-53, 9 s. 2009.
• Nakladatel: NOVPRESS s.r.o.

Další údaje

• Originální 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: complexity, mean-payoff games, randomized algorithms
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

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.

Anotace č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