The worst-case running time of the random simplex algorithm is exponential in the height

Abstract

The random simplex algorithm for linear programming proceeds as follows: at each step, it moves from a vertex v of the polytope to a randomly chosen neighbor of v, the random choice being made from those neighbors of v that improve the objective function. We exhibit a polytope defined by n constraints in three dimensions with height O(log n), for which the expected running time of the random simplex algorithm is Ω( n log n). © 1995.