Solving Linear Programs in the Current Matrix Multiplication Time
share
This paper shows how to solve linear programs of the form _Ax=b,x≥0 c^ x with n variables in time O^*((n^ω+n^2.5-α/2+n^2+1/6) (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^ω(n/δ)) time. When ω = 2, our algorithm takes O^*(n^2+1/6(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^T(AWA^)^-1A√(W) in sub-quadratic time under ℓ_2 multiplicative changes in the diagonal matrix W.
READ FULL TEXT