In an undergrad class on linear programming, we learned about the simplex and ellipsoid methods for solving linear programs (LPs). I know that the simplex method is generally faster than the ellipsoid method, but its worst-case complexity is much slower. In searching the web and the book we used I haven't been able to find much beyond that summary.

Can anyone give me a situation in which the simplex method devolves into an exponential running time, which would make it slower than the ellipsoid method? An example of an actual LP would be awesome, but any info is greatly appreciated.

Also, please let me know if this is not the right SE for this specific question. I didn't see much at all on the ellipsoid method when searching before posting this question.

  • 2
    $\begingroup$ From en.wikipedia.org/wiki/Simplex_algorithm#Efficiency: "However, in 1972, Klee and Minty[32] gave an example, the Klee–Minty cube, showing that the worst-case complexity of simplex method as formulated by Dantzig is exponential time." $\endgroup$ – Rahul Jun 15 at 10:01
  • $\begingroup$ Reccho, if you don't any answer here, you can also consider to ask at OR.SE. $\endgroup$ – Marcus Ritt Jun 15 at 17:47
  • $\begingroup$ cstheory.stackexchange.com $\endgroup$ – Rodrigo de Azevedo Jun 15 at 18:03
  • $\begingroup$ Thank you for all the comments. I think the Klee-Minty cube is the best example I can find, and I will also check out the other SE. I appreciate all the answers :) $\endgroup$ – Reccho Jun 16 at 18:46

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.