Practical polynomial time algorithms for linear complementarity problems

In this paper the authors first propose three practical algorithms for linear complementarity problems, which are based on the polynomial time method of Kojima, Mizuno and Yoshise, and compare them by showing the computational complexities. Then they modify two of the algorithms in order to accelerate them. Through the computational experiments for three types of linear complementarity problems, the authors compare the proposed algorithms in practice and see the efficiency of the modified algorithms. They also estimate the practical computational complexity of each algorithm for each type of problem.