2005-05: Linear Complementarity Algorithms for Mean Payoff Games

DIMACS TR: 2005-05

Linear Complementarity Algorithms for Mean Payoff Games

Authors: Henrik Bjorklund, Ola Svensson and Sergei Vorobyov

ABSTRACT
We suggest new pseudopolynomial and subexponential algorithms for Mean Payoff Games (MPGs). The algorithms are based on representing the MPGs decision problem in the forms of non-standard and standard LCPs, Linear Complementarity Problems (find $w,z\geq 0$ satisfying $w=Mz+q$ and $w^T\cdot z=0$), and monotonic iterative propagation of slack updates.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-05.ps.gz

DIMACS Home Page