I had this exam question last semester, and it's still bothering me:

For every natural number $n$, you want an LP (not necessarily with $n$ inequalities) such that simplex cannot solve it in time $\operatorname{poly}(n)$, but ellipsoid method can.

I know ellipsoid method will always run in polynomial time, but I can't figure out how to make simplex take exponential time, regardless of the pivot rule used.

The way I understood the problem was to create an LP that will force the Simplex method to run in exponential time, while the Ellipsoid method will run in polynomial. This should hold for all possible pivot rules. I know the Klee-Minty cube slows down Simplex for some pivot rules, but not all. Is it possible to create an LP that does this?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.