Solving linear programs in the current matrix multiplication time / Michael B. Cohen; Yin Tat Lee; Zhao Song
Si trova su / Altri legami
© 2021 ACM.This article shows how to solve linear programs of the form minAx=b,x⥠0x with n variables in time Oâ—((n4omega;+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: •We define a stochastic central path method. •We show how to maintain a projection matrix WAÄSCurrency sign (AWAS W in sub–quadratic time under â“2 multiplicative changes in the diagonal matrix W.
