<p>It seems that K.M.Anstreicher has improved the result to $O((n^3/\ln n)L)$ in <a href="http://epubs.siam.org/doi/abs/10.1137/S1052623497323194?journalCode=sjope8">Anstreicher, Kurt M. "Linear programming in O ([n3/ln n] L) operations." SIAM Journal on Optimization 9, no. 4 (1999): 803-812.</a>. I have not read this paper, but I hope that this answer will help you in some extent.</p>

CC BY-SA 3.0
2014-08-31T15:06:44.770Z
2014-08-31T15:06:44.770Z
jet
<p>According to <a href="http://link.springer.com/book/10.1007%2F978-94-011-1134-8">D. den Hertog, Interior Point Approach to Linear, Quadratic and Convex Programming, 1994</a>, a linear program with $n$ variables, $n$ constraints and precision $L$ is solvable in $O(n^3L)$ time. Has that been improved upon?</p>

<cc.complexity-theory><reference-request><linear-programming>
Is cubic complexity still the state of the art for LP?
Aryeh
# Is cubic complexity still the state of the art for LP?

(Asked by: username_0 on 2014-01-06)

According to [D. den Hertog, Interior Point Approach to Linear, Quadratic and Convex Programming, 1994](http://link.springer.com/book/10.1007%2F978-94-011-1134-8), a linear program with $n$ variables, $n$ constraints and precision $L$ is solvable in $O(n^3L)$ time. Has that been improved upon?

**Tags:** cc.complexity-theory, reference-request, linear-programming


---

## 1 answers

### Answer by username_1 on 2014-08-31. Score: 6 | Accepted answer

It seems that K.M.Anstreicher has improved the result to $O((n^3/\ln n)L)$ in [Anstreicher, Kurt M. "Linear programming in O ([n3/ln n] L) operations." SIAM Journal on Optimization 9, no. 4 (1999): 803-812.](http://epubs.siam.org/doi/abs/10.1137/S1052623497323194?journalCode=sjope8). I have not read this paper, but I hope that this answer will help you in some extent.


---

