6
$\begingroup$

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

$\endgroup$
  • 1
    $\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
  • 1
    $\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
  • 1
    $\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
  • 1
    $\begingroup$ The result due to Spielman and Teng has explained why simplex method is efficient in practice arxiv.org/pdf/cs/0111050.pdf Title : Smoothed Analysis of Algorithms: Why the Simplex Algorithm usually Takes Polynomial Time. $\endgroup$ – Zhao Song Apr 21 at 23:18
  • 1
    $\begingroup$ This lecture notes contain a detailed history of LP algorithm in theory, cs.utexas.edu/~ecprice/courses/331/slides/04-20.pdf $\endgroup$ – Zhao Song Apr 29 at 0:06
6
$\begingroup$

The best possible (I believe) is by Michael Cohen, Yin Tat Lee, and Zhao Song: Solving linear program in the current matrix multiplication time. https://arxiv.org/abs/1810.07896 (STOC 2019) Hope this helps.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The result by Cohen, Lee and Song has been reproduced via a different method, see this paper arxiv.org/pdf/1905.04447.pdf $\endgroup$ – Zhao Song Apr 21 at 23:13
  • $\begingroup$ The 2+1/6 has been improved to 2+1/18 in a recent work by Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. The title is Faster Dynamic Matrix Inverse for Faster LPs, and the link is arxiv.org/pdf/2004.07470.pdf $\endgroup$ – Zhao Song May 19 at 0:32
2
$\begingroup$

Brand's 2020 result derandomized the Cohen, Lee and Song result. Here is the link https://arxiv.org/pdf/1910.11957.pdf

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