25
$\begingroup$

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?

$\endgroup$

1 Answer 1

6
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.