3
$\begingroup$

What is the computational complexity of solving a linear program with $m$ constraints in $n$ variables?

$\endgroup$
  • $\begingroup$ There are (weak)polynomial times algorithms that find the solutions by moving a point in the interior of the simplex. I don't know what is the minimum exponent possible. $\endgroup$ – user647486 Apr 26 '19 at 17:53
  • $\begingroup$ Though it’s worth mentioning that the most common linear programming algorithm—the simplex—method, os exponential in its worst case. $\endgroup$ – David M. Apr 28 '19 at 3:43
  • $\begingroup$ Thank you, but here I am speaking about the theoretical complexity of linear programming not algorithms. For example, it is known (to the best of my knowledge) that solving a quadratic program is equivalent to solving a system of linear equations, so the complexity of quadratic programming is about O(n^3). Is there any similar result for linear programming ? $\endgroup$ – user486789 Apr 28 '19 at 17:40
4
$\begingroup$

The best possible (I believe) is by Cohen, Lee, and Song: https://arxiv.org/abs/1810.07896

Hope this helps.

$\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.