Lemke Paths on Simple Polytopes

Lemke paths are often used in the solution of nonlinear programming problems. We investigate a number of properties of Lemke paths, motivated by the d-step conjecture for linear programming. Some negative results are presented, including families of Lemke paths, for which the length of the shortest grows exponentially, joining pairs of vertices of a sequence of polytopes.