This paper proposes an O(n3L) algorithm which is a modification of the path following algorithm for a linear complementarity problem. The path following algorithm has to take a short step size in each iteration in order to bound the number of overall arithmetic operations by O(n3L). In practical computation, it can determine the step size adaptively. Mizuno, Yoshise, and Kikuchi reported that such an adaptive algorithm required about O(L) iterations for some test problems. The paper shows that it can use a rank one update technique in the adaptive algorithm so that the number of overall arithmetic operations is theoretically bounded by O(n3L).
