Solving Linear Programs in the Current Matrix Multiplication Time

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 √ W A ⊤ (AWA ⊤) −1 A √ W in sub-quadratic time under 2 multiplicative changes in the diagonal matrix W.