Faster Algorithm for Mean-Payoff Games

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.

Authors	CHALOUPKA Jakub BRIM Luboš
Year of publication	2009
Type	Article in Proceedings
Conference	Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)
MU Faculty or unit	Faculty of Informatics
Citation
Web	http://drops.dagstuhl.de/opus/volltexte/2009/2348/
Field	Informatics
Keywords	mean-payoff games; randomized algorithms; complexity
Description	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.
Related projects:	Highly Parallel and Distributed Computing Systems Verification and Analysis of Large-Scale Computer Systems