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