The Linear Complementarity Problem, Lemke Algorithm, Perturbation, and the Complexity Class PPAD
We present a single sufficient condition for the processability of the Lemke algorithm for semimonotone Linear Complementarity problems (LCP) which unifies several sufficient conditions for a number of well known subclasses of semimonotone LCPs. In particular, we study the close relationship of these problems to the complexity class PPAD. Next, we show that these classes … Read more