The Worst-Case Running Time of the Random Simplex Algorithm Is Exponential in the Height

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 $\Omega(n/\log n)$.