我们给出在 $m$ 条边的有向图上，针对 $k$ 种商品的多商品流问题（包括并发多商品流和最大多商品流）计算乘法 $(1-\epsilon)$ 近似解的 $m^{1+o(1)}k\epsilon^{-1}$ 时间算法。为实现该结果，我们提出了两套可能独立有价值的优化工具。第一套工具改进了求解 $\ell_{q,p}$ 回归的高精度方法，只需对每个块调用一次高精度凸最小化 oracle $\tilde{O}_{q,p}(k)$ 次（$\tilde{O}_{q,p}(\cdot)$ 隐含仅与 $q,p$ 或 $\mathrm{poly}(\log m)$ 相关的因子），相较于 [Chen‑Ye, ICALP 2024] 的 $\tilde{O}_{q,p}(k^2)$ 提升显著。由此我们得到首个几乎线性时间求解有向图上 $\ell_{q,p}$ 流的高精度算法。第二套工具将近似求解复合 $\ell_{1,\infty}$ 回归的问题转化为求解 $m^{o(1)}\epsilon^{-1}$ 个复合 $\ell_{q,p}$ 回归实例。该方法基于最近在求解 box‑simplex 游戏的进展 [Jambulapati‑Tian, NeurIPS 2023]，并结合了 [Sherman, STOC 2017] 引入的面积凸正则化器，以更快的收敛速率处理约束版本的问题。将上述技术精心组合，即得到我们针对有向图的多商品流算法。
点评