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?

asked Apr 30, 2020 at 13:05
$\endgroup$

2 Answers 2

4
$\begingroup$

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

answered Apr 30, 2020 at 13:41
$\endgroup$
4
$\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.

answered Apr 30, 2020 at 17:16
$\endgroup$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.