A new polynomial time method for a linear complementarity problem

The purpose of this paper is to present a new polynomial time method for a linear complementarity problem with a positive semi-definite matrix. The method follows a sequence of points. If we generate the sequence on a path, we can construct a path following method, and if we generate the sequence based on a potential function, we can construct a potential reduction method. The method has the advantage that it requires at most iterations for any initial feasible point whose components lie between 2^–O(L) and 2^O(L).Research was supported in part by Grant-in-Aids for Encouragement of Young Scientists (63730014) and for General Scientific Research (63490010) of The Ministry of Education, Science and Culture.