45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04) Random Edge Can Be Exponential on Abstract Cubes Rome, Italy October 17-October 19 ISBN: 0-7695-2228-9
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.56
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 Wiliamson Hoke [27] and by Kalai [16] 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 ? n^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.
Citation:
Jiří Matoušek, Tibor Szabó, "Random Edge Can Be Exponential on Abstract Cubes," focs, pp.92-100, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb