Georgia Institute of Technology College of Sciences

One of the most interesting aspects of the Linear Complementarity Problem (LCP) is its range from relatively easy problems such as linear and convex quadratic programming problems to NP-hard problems. A major effort in LCP theory had been the study of the Lemke algorithm, a simplex-like algorithm which is guaranteed to terminate in finite number of iterations but not necessarily with a solution (or a certificate that no solution exists). Over the years, many subclasses of LCP were proven to be workable by the Lemke algorithm. Those subclasses were often characterized as ‘nice’ even when no polynomial upper bound for the algorithm was known to exist. In fact, for most of these classes, instances with exponential number of steps had been discovered. In this talk, I’ll discuss the close connection between these classes and the PPAD (Polynomial-time Parity Argument Directed) complexity class. The discovery that computing Nash equilibrium (which is an LCP) is PPAD complete is particularly significant in analyzing the complexity of LCP. I’ll also discuss the LCP reduction-via-perturbation technique and its relation to the PPAD class and the Lemke Algorithm. This talk is based on a joint work with Sushil Verma.