Solving Tall Dense Linear Programs in Nearly Linear Time

Jan van den Brand, Yin Tat Lee, Aaron Sidford +1

In this paper we provide an $\tilde{O}(nd+d^3)$ time randomized algorithm for solving linear programs with $d$ variables and $n$ constraints with high probability. To obtain this…