Faster Algorithm for Mean-Payoff Games

• 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
• 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