Faster Algorithm for Mean-Payoff Games

Chaloupka, Jakub; Brim, Luboš

doi:10.4230/DROPS.MEMICS.2009.2348

Document

Faster Algorithm for Mean-Payoff Games

Authors Jakub Chaloupka, Luboš Brim

Part of: Volume: Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09) (MEMICS 2009)
Part of: Series: Open Access Series in Informatics (OASIcs)
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
Publication Date: 2009-12-15

PDF

File

DROPS.MEMICS.2009.2348.pdf

Filesize: 422 kB
9 pages

Document Identifiers

DOI: 10.4230/DROPS.MEMICS.2009.2348
URN: urn:nbn:de:0030-drops-23481

Author Details

Jakub Chaloupka

Luboš Brim

Cite As Get BibTex

Jakub Chaloupka and Luboš Brim. Faster Algorithm for Mean-Payoff Games. In Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09). Open Access Series in Informatics (OASIcs), Volume 13, pp. 53-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009) https://doi.org/10.4230/DROPS.MEMICS.2009.2348

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.

Subject Classification

Keywords

Mean-payoff games
randomized algorithms
computational complexity

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail