Department of Computer Science | Institute of Theoretical Computer Science

We study the behavior of simple principal pivoting methods for the
P-matrix linear complementarity problem (P-LCP). We solve an open
problem of Morris by showing that Murty's least-index pivot rule
(under any fixed index order) leads to a quadratic number of
iterations on Morris's highly cyclic P-LCP examples. We then show
that on K-matrix LCP instances, \emph{all} pivot rules require only
a linear number of iterations. As the main tool, we employ
\emph{unique-sink orientations} of cubes, a useful combinatorial
abstraction of the P-LCP.