D 2009

Faster Algorithm for Mean-Payoff Games

CHALOUPKA, Jakub and Luboš BRIM

Basic information

Original name

Faster Algorithm for Mean-Payoff Games

Name in Czech

Rychlejší algorimus pro mean-payoff hry

Authors

CHALOUPKA, Jakub (203 Czech Republic) and Luboš BRIM (203 Czech Republic, guarantor)

Edition

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

Publisher

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

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

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

References:

RIV identification code

RIV/00216224:14330/09:00029949

Organization unit

Faculty of Informatics

ISBN

978-3-939897-15-6

Keywords in English

mean-payoff games; randomized algorithms; complexity

Tags

Tags

International impact, Reviewed
Změněno: 11/3/2010 16:18, RNDr. Jakub Chaloupka, Ph.D.

Abstract

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.

In Czech

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í.

Links

GA201/09/1389, research and development project
Name: Verifikace a analýza velmi velkých počítačových systémů
Investor: Czech Science Foundation, Verification and Analysis of Large-Scale Computer Systems
MSM0021622419, plan (intention)
Name: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems