The linear complementarity problem (LCP) belongs to the class of NP -hard problems. Therefore, we cannot expect a polynomial time solution method for LCPs without requiring some special property of the matrix of the problem. We show that the dual LCP can be solved in polynomial time if the matrix is row sufficient; moreover, in this case, all feasible solutions are complementary. Furthermore, we present an existentially polytime (EP) theorem for the dual LCP with arbitrary matrix.
|Journal||Journal of Optimization Theory and Applications|
|Publication status||Published - 2009|