Solving Linear Programs in the Current Matrix Multiplication Time

Abstract

This paper shows how to solve linear programs of the form ${\min }_{Ax=b,x\ge 0}{c}^{\top }x$ with $n$ variables in time $$O^{\ast }((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})\log (n/\delta ))$$ where $\omega$ is the exponent of matrix multiplication, $\alpha$ is the dual exponent of matrix multiplication, and $\delta$ is the relative accuracy. For the current value of $\omega \sim 2.37$ and $\alpha \sim 0.31$, our algorithm takes $O^{\ast }(n^{\omega }\log (n/\delta ))$ time. When $\omega =2$, our algorithm takes $O^{\ast }(n^{2+1/6}\log (n/\delta ))$ time. Our algorithm utilizes several new concepts that we believe may be of independent interest: $\bullet$ We define a stochastic central path method. $\bullet$ We show how to maintain a projection matrix $\sqrt{W}{A}^{\top }(AW{A}^{\top }{)}^{-1}A\sqrt{W}$ in sub-quadratic time under ${\ell }_2$ multiplicative changes in the diagonal matrix $W$.

STOC 2019, JACM 2020