Khachiyan Ellipsoid algorithm ( Linear Programming)

Time Complexity

$O(n^{6} * L^{2} \log L \log\log L)$

Space Complexity

$O(nmL)$ words

(see orginal paper (noting that O(alpha*log(H*alpha)) = O(L)))

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

1979

Reference

https://www.sciencedirect.com/science/article/abs/pii/0041555380900610