






















We give the first local algorithm for computing multi-commodity flow and apply it to obtain a $(1+ε)$-approximate algorithm for computing a $k$-commodity flow on an expander with $m$ edges in $(m+ε^{-3}k^3D)n^{o(1)}$ time, where $D$ is the total demand. This is the first $(1+ε)$-approximate algorithm that breaks the $km$ multi-commodity flow barrier, albeit only on expanders. All previous algorithms either require $Ω(km)$ time or a big constant approximation. Our approach is by localizing Sherman's flow algorithm when put into the Multiplicative Weight Update (MWU) framework. We show that, on each round of MWU, the oracle could instead work with the *rounded weights* where all polynomially small weights are rounded to zero. Since there are only few large weights, one can implement the oracle call with respect to the rounded weights in sublinear time. This insight is generic and may be of independent interest.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。