HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Complexity of linear programming

Submitted by: @import:stackexchange-cs··
0
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?

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.