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.
DIMACS Home Page