Solving Linear Programs in the Current Matrix Multiplication Time
Michael B. Cohen, Yin Tat Lee, Zhao Song
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 √ W A ⊤ ( AWA ⊤ ) −1 A √ W in sub-quadratic time under \ell 2 multiplicative changes in the diagonal matrix W .