Karmarkar's partial updating scheme is applied to a polynomial, superlinearly convergent algorithm for monotone LCP. This modification reduces the bound on the number of arithmetic operations necessary to achieve epsilon optimality by a factor of sqrt(n). The complementarity gap sequence generated by the resulting algorithm converges q-quadratically to zero if the LCP is nondegenerate with a strictly complementary optimal solution. In general, the convergence rate is q-superlinear if the iterates are assumed to converge to a strictly complementary optimal solution.
To appear in SIAM Journal of Optimization.