License
When quoting this document, please refer to the following
DOI: 10.4230/DROPS.MEMICS.2009.2348
URN: urn:nbn:de:0030-drops-23481
URL: http://drops.dagstuhl.de/opus/volltexte/2009/2348/
Go to the corresponding OASIcs Volume Portal


Chaloupka, Jakub ; Brim, Luboš

Faster Algorithm for Mean-Payoff Games

pdf-format:
Document 1.pdf (422 KB)


Abstract

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.

BibTeX - Entry

@InProceedings{chaloupka_et_al:OASIcs:2009:2348,
  author =	{Jakub Chaloupka and Lubo{\v{s}} Brim},
  title =	{{Faster Algorithm for Mean-Payoff Games}},
  booktitle =	{Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)},
  pages =	{53--61},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-15-6},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{13},
  editor =	{Petr Hlinen{\'y} and V{\'a}clav Maty{\'a}{\v{s}} and Tom{\'a}{\v{s}} Vojnar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2348},
  URN =		{urn:nbn:de:0030-drops-23481},
  doi =		{http://dx.doi.org/10.4230/DROPS.MEMICS.2009.2348},
  annote =	{Keywords: Mean-payoff games, randomized algorithms, computational complexity}
}

Keywords: Mean-payoff games, randomized algorithms, computational complexity
Seminar: Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)
Issue Date: 2009
Date of publication: 15.12.2009


DROPS-Home | Fulltext Search | Imprint Published by LZI