Faster Algorithm for Mean-Payoff Games

• Authors: CHALOUPKA Jakub; BRIM Luboš
• Year of publication: 2009
• Type: Article in Proceedings
• Conference: MEMICS 2009
• MU Faculty or unit: Faculty of Informatics
• 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