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\geq0} c^\top x$ with $n$ variables in time $$O^*((n^ω+n^{2.5-α/2}+n^{2+1/6}) \log(n/δ))$$ where $ω$ is the exponent of matrix multiplication, $α$ is the dual exponent of matrix multiplication, and $δ$ is the relative accuracy. For the current value of $ω\sim2.37$ and $α\sim0.31$, our algorithm takes $O^*(n^ω \log(n/δ))$ time. When $ω= 2$, our algorithm takes $O^*(n^{2+1/6} \log(n/δ))$ 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}(AWA^{\top})^{-1}A\sqrt{W}$ in sub-quadratic time under $\ell_{2}$ multiplicative changes in the diagonal matrix $W$.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.