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)$.

By: Andrei Z. Broder (Digital Systems Res. Ctr., Palo Alto, CA), Martin E. Dyer (Leeds Univ., Eng.), Alan M. Frieze (Carnegie Mellon Univ.), Prabhakar Raghavan and Eli Upfal (Weizmann Inst. of Sci., Rehovot, Israel)

Published in: Information Processing Letters, volume 56, (no 2), pages 79-81 in 1995

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to .