1

I know that there are cases in which the simplex methods, in linear programming, needs exponential time to calculate the solution.

So why is simplex method considered a P problem ?

Koinos
  • 191
  • 1
    In the worst case, the simplex method has exponential running time. Think about a ball and the algorithm running from vertex to vertex. In the average case, however, the simplex method has polynomial running time. – Wuestenfux Oct 02 '18 at 07:21
  • Is this sufficient to put it in the P class ? – Koinos Oct 02 '18 at 07:23

1 Answers1

3

Linear Programming as such is in P because there are other algorithms which can solve Linear Programs (LPs) in polynomial time, for example interior points methods. The simplex, however, has an exponential running time for worst-case examples (such as the Klee-Minty-cube). Since other algorithms exist which can always solve an LP in polynomial time, LPs are in P.

Even though these worst-case examples for the simplex method exist, it shows very good running times in practice. One further advantage of the simplex method is that you can warm-start it if you have to make slight changes to your problem. This does not work with interior points methods which is why the simplex is often more attractive to use in practice, despite its potential exponential running time.

YukiJ
  • 2,529