摘要
针对具有整数多项式边界成本和容量的 $n$-顶点 $m$-边图，我们提出了一种随机并行算法，用于解决最小费用流问题，其工作量为 $\tilde O(m+n^{1.5})$，深度为 $\tilde O(\sqrt{n})$。在中等密度图上（$m \approx n^{1.5}$），该算法首次实现了近线性工作和亚线性深度的结合。之前的算法要么在工作量上接近最优但高度顺序化 [Chen, Kyng, Liu, Peng, Gutenberg, Sachdev, FOCS'22]，要么在深度上达到亚线性但工作量超线性 [Lee, Sidford, FOCS'14], [Orlin, Stein, Oper. Res. Lett.'93]。
我们的结果还改善了最大流、二分图最大匹配、最短路径和可达性等特殊情况。值得注意的是，之前实现最短路径和可达性的近线性工作算法的深度均为 $n^{o(1)} \times \sqrt{n}$ [Fischer, Haeupler, Latypov, Roeyskoe, Sulser, SOSA'25], [Liu, Jambulapati, Sidford, FOCS'19]。
我们的算法基于 [van den Brand, Lee, Liu, Saranurak, Sidford, Song, Wang, STOC'21] 的并行实现。一个重要的构建块是动态并行扩展器分解，我们展示了如何从 [Chen, Meierhans, Probst Gutenberg, Saranurak, SODA'25] 的最新并行扩展器分解中获得它。
博主点评： 本文提出的算法在处理密集图的最小费用流问题上实现了重要的理论突破，尤其是在工作量和深度的平衡上。未来的研究可以进一步探索此算法在其他图论问题中的应用潜力。