RANDOM EDGE can be exponential on abstract cubes

Abstract

We prove that RANDOM EDGE, the simplex algorithm that always chooses a random improving edge to proceed on, can take a mildly exponential number of steps in the model of abstract objective functions. We define an abstract objective function on the n-dimensional cube for which the algorithm, started at a random vertex, needs at least exp(const.n^{1/3}) steps with high probability.

Keywords

• RANDOM
• exponential
• abstract
• cubes