25

According to D. den Hertog, Interior Point Approach to Linear, Quadratic and Convex Programming, 1994, a linear program with $n$ variables, $n$ constraints and precision $L$ is solvable in $O(n^3L)$ time. Has that been improved upon?

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
Aryeh
  • 10,494
  • 1
  • 27
  • 51

1 Answers1

6

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.. I have not read this paper, but I hope that this answer will help you in some extent.

jet
  • 86
  • 1
  • 4