A polynomial-time algorithm for a class of linear complementarity problems

Given an n×n matrix M and an n-dimensional vector q, the problem of finding n-dimensional vectors x and y satisfying y=Mx+q, x≥0, y≥0, xiyi=0 (i=1,2,...,n) is known as a linear complementarity problem. Under the assumption that M is positive semi-definite, this paper presents an algorithm that solves the problem in O(n³L) arithmetic operations by tracing the path of centers, {(x,y)∈S: xiyi=μ (i=1,2,...,n) for some μ∈0∈ of the feasible region S={(x,y)≥0: y=Mx+q∈, where L denotes the size of the input data of the problem.