An Exponential Lower Bound for Zadeh's pivot rule

Yann Disser, Oliver Friedmann, Alexander V. Hopp

The question whether the Simplex Algorithm admits an efficient pivot rule remains one of the most important open questions in discrete optimization. While many natural, determinist…