Tag Archives: The simplex algorithm

Subexponential Lower Bound for Randomized Pivot Rules!

Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick have managed to prove subexponential lower bounds of the form for the following two basic randomized pivot rules for the simplex algorithm! This is the first result of its kind and deciding … Continue reading

Posted in Computer Science and Optimization, Convex polytopes, Games | Tagged , | 11 Comments