Solving Linear Programs in the Current Matrix Multiplication Time

Abstract

This article shows how to solve linear programs of the form min_{Ax=b,x≥ 0} c^⊤ 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 ω δ 2.37 and α δ 0.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: • We define a stochastic central path method. • We show how to maintain a projection matrix √ WA^⊤ (AWA^⊤)⁻¹A√ W in sub-quadratic time under \ell₂ multiplicative changes in the diagonal matrix W.