


























This paper shows how to solve linear programs of the form $\min_{Ax=b,x\geq0} c^\top 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 $ω\sim2.37$ and $α\sim0.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: $\bullet$ We define a stochastic central path method. $\bullet$ We show how to maintain a projection matrix $\sqrt{W}A^{\top}(AWA^{\top})^{-1}A\sqrt{W}$ in sub-quadratic time under $\ell_{2}$ multiplicative changes in the diagonal matrix $W$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。