Random edge can be exponential on abstract cubes

摘要

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 (introduced by K. W. Hoke (1998) and by G. Kalai (1988) under different names). 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 /spl middot/ n/sup 1/3/) steps with high probability. The best previous lower bound was quadratic. So in order for random edge to succeed in polynomial time, geometry must help.