patternMinor
Complexity of linear programming
Viewed 0 times
linearcomplexityprogramming
Problem
I have a basic question, if I can model a problem $(P)$ by a linear program, can we say that $(P)$ is polynomial?
Linear programs can be solved using simplex, and it was proved that simplex run in exponential time for some instances, so why some references assume that linear programming is polynomial?
Linear programs can be solved using simplex, and it was proved that simplex run in exponential time for some instances, so why some references assume that linear programming is polynomial?
Solution
There exist polynomial time algorithms for solving linear programs. These include the ellipsoid algorithm and interior-point methods. See Wikipedia.
Context
StackExchange Computer Science Q#124996, answer score: 3
Revisions (0)
No revisions yet.