Details

Autor(en) / Beteiligte

• Cohen, Michael B.
• Lee, Yin Tat
• Song, Zhao

Titel

Solving linear programs in the current matrix multiplication time

Ist Teil von

• Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019, p.938-942

Ort / Verlag

New York, NY, USA: ACM

Erscheinungsjahr

2019

Quelle

ACM Digital Library

Beschreibungen/Notizen

• This paper shows how to solve linear programs of the form minAx=b,x≥0 c⊤x with n variables in time O*((nω+n2.5−α/2+n2+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*(n2+1/6 log(n/δ)) time. Our algorithm utilizes several new concepts that we believe may be of independent interest: (1) We define a stochastic central path method. (2) We show how to maintain a projection matrix √W A⊤(AWA⊤)−1A √W in sub-quadratic time under ℓ2 multiplicative changes in the diagonal matrix W.