The Equivalence of Dantzig's Self-Dual Parametric Algorithm for Linear Programs to Lemke's Algorithm for Linear Complementarity Problems Applied to Linear Programs.

Dantzig has asserted that his self-dual parametric algorithm for solving a linear program is equivalent to Lemkes method for solving a linear complementary problem when the latter is applied to solve a linear program. This paper formally proves that Dantzigs assertion is correct--specifically that the point reached along the solution path after 2t iterations of Lemkes method is identical with the point reached after t iterations of Dantzigs method. Keywords Linear programming Lemkes method Self dual parametric algorithm Linear complementarity problems.