## DIMACS TR: 2005-20

##
A Subexponential Algorithm for a Subclass of P-Matrix
Generalized Linear Complementarity Problems

### Authors: Ola Svensson and Sergei Vorobyov

**
ABSTRACT
**

We define a nontrivial (polynomially time recognizable, but not known
to be polynomial time solvable) subclass of P-matrix Generalized
(Vertical) Linear Complementarity Problems, which we call D-matrix
GLCPs. D-matrices have nonnegative entries and strict row diagonal
dominance. In general, P-matrix LCPs and GLCPs are not known to be
polynomial, or even subexponential time solvable, and the property
``to be a P-matrix'' is coNP-complete.
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
time.

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

DIMACS Home Page