We present $m^{1+o(1)}k\epsilon^{-1}$‑time algorithms that compute multiplicative $(1-\epsilon)$‑approximate solutions for multi‑commodity flow problems with $k$ commodities on directed graphs with $m$ edges, covering both concurrent and maximum multi‑commodity flow. To achieve these results we introduce two new optimization toolkits of independent interest. The first toolkit improves the high‑accuracy solution of $\ell_{q,p}$‑regression, requiring only $\tilde{O}_{q,p}(k)$ queries to a high‑accuracy convex minimization oracle per block (where $\tilde{O}_{q,p}(\cdot)$ hides factors depending solely on $q$, $p$, or $\mathrm{poly}(\log m)$), improving over the $\tilde{O}_{q,p}(k^2)$ bound of [Chen‑Ye, ICALP 2024]. This yields the first almost‑linear‑time algorithm for solving $\ell_{q,p}$ flows on directed graphs to high accuracy. The second toolkit reduces the problem of approximately solving composite $\ell_{1,\infty}$‑regression to solving $m^{o(1)}\epsilon^{-1}$ instances of composite $\ell_{q,p}$‑regression. The approach builds on recent advances in solving box‑simplex games [Jambulapati‑Tian, NeurIPS 2023] and the area convex regularizer introduced in [Sherman, STOC 2017], achieving faster rates for constrained variants. Careful integration of these techniques yields our directed multi‑commodity flow algorithm.
Review