3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

There exist polynomial time algorithms for solving linear programs. These include the ellipsoid algorithm and interior-point methods. See Wikipedia.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

It's because there are other algorithms (like interior point methods) which run in polynomial time for solving the problem. Even with that being said, it is perfectly possible that the simplex method will outperform them in practice.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.