We describe the first strongly subexponential randomized algorithm for D-matrix GLCPs. As a lower bound, we show that simple stochastic games, a long standing problem in NP intersect coNP, unknown to be polynomial, is subsumed by D-matrix GLCPs.
As an important application, our D-matrix GLCP algorithm gives the
best currently available algorithm for computing values of simple
stochastic games. At present, the D-matrix GLCP is the only known
nontrivial subclass of the P-matrix GLCP solvable in subexponential
Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-20.ps.gz