最快网络流算法速度接近理论极限

而且，它依然能在最低成本的前提下，精准计算出网络的最大运输流量。

这一突破性进展来自苏黎世联邦理工学院计算机科学系的Rasmus Kyng团队，在业界被亲切称为“京爷”。

实际上，早在两年前，京爷团队的上一代研究成果就已经引起广泛关注，并被《Quanta Magazine》评选为当年计算机科学领域的十大发现之一。

就连网络流算法领域的先驱Daniel A. Spielman也不禁为之点赞。

就在最近，这支团队在ACM计算理论研讨会（STOC）上发布了该算法的“进化版”——

无论网络中的路径是增加还是删除，该算法都能以最低成本和最大传输流量的方式，在几乎线性的时间内完成计算。

这就像徒步旅行——无论道路变得多么复杂或陡峭，你依然能保持高速前进，轻松抵达终点。

苏黎世联邦理工学院官方对此给出了高度评价：

那么，京爷团队究竟是如何实现这一突破的？

迄今最快的网络流算法

网络流，本质上是图论中的一种理论与方法，专门研究网络上的最优化问题。

该问题最早可追溯至1955年，当时T.E.哈里斯在分析铁路最大通量时，为寻找两点间的最大运输量而提出。

1956年，L.R.福特和D.R.富尔克森等人提出了解决这类问题的算法，网络流理论由此正式确立。

此外，网络流算法在解决现实场景中问题时的价值极为显著。

例如，你希望利用欧洲运输网络，找到一条最快且成本最低的路径，将尽可能多的货物从哥本哈根运至米兰——此时网络流算法便能大显身手。

对于此类问题，以往计算最佳流量所需的时间，甚至远超处理网络数据本身的时间。

随着网络规模日益庞大且复杂度持续提升，计算时间的增长速度远远超过了问题本身实际规模的增速。

这正是目前一些计算机无法应对网络流量计算的根本原因。

然而，京爷团队提出的算法彻底打破了这一僵局——

不仅从读取网络数据到得出解决方案所需的“额外”计算时间几乎可以忽略不计，即便是重新设计路由或新增路由，也基本不会产生额外开销。

原则上，所有计算方法都面临一个共同挑战：必须经过多次迭代分析网络，才能找到最优流量和最低成本路径。

在京爷团队之前，研究者们通常只能在两种核心策略中二选一：

一种方法以铁路网络为模型，每次迭代都对整个网络进行计算并调整交通流量；另一种方法则受电网中电力流的启发，同样每次迭代计算整个网络，但通过统计平均值修改每个部分的流量。

而京爷团队的做法是——成年人不做选择，他们融合了两种方法的优势，打造出全新的算法：

这项最新研究提出了一系列针对增量图（incremental graphs）问题的近线性时间算法。

增量图是指随时间动态变化的有向图，其结构主要通过边的插入操作来改变。

论文中提出的算法主要解决以下问题：

环检测（Cycle Detection）：识别图中是否存在环。强连通分量维护（Strongly Connected Component Maintenance, SCCs）：维持图中的强连通分量状态。单源最短路径（s-t Shortest Path）：计算从单源到单目标的最短路径。最小成本流（Minimum-Cost Flow）：在容量限制下，寻找成本最小的流。

论文的主要技术贡献在于提出了一种确定性数据结构，能够在完全动态图中，针对每次更新，以摊销近线性时间返回一个近似最小比率环。

结合Brand-Liu-Sidford（STOC 2023）的内点方法框架，该论文给出了第一个能够决定增量图中最小成本流是否达到给定阈值的算法。

此外，团队还设计并采用了新的数学工具，进一步提升了算法的速度。

结果表明，论文提出的算法在理论上为增量图问题提供了高效的解决方案，其时间复杂度显著优于以往的方法。

然而，京爷团队为以往无法有效计算的超大规模问题奠定基础，只是这些更快网络流算法所产生的影响之一。

更深层的影响在于：它们正在从根本上改变计算机执行复杂任务的计算方式。

正如加州大学伯克利分校的一个国际研究团队所评价的：

在过去的十年中，理论计算机科学在基础问题上为获得可证明的快速算法，经历了理论基础层面的一场革命。

关于研究团队

这项研究共有三位来自苏黎世联邦理工学院的作者。

其中的核心人物京爷——Rasmus Kyng，现为苏黎世联邦理工学院计算机科学系助理教授，研究方向涵盖图问题与凸优化的快速算法、概率与差异理论、细粒度复杂性理论以及机器学习应用。

Rasmus Kyng

另一位主要贡献者是Maximilian Probst博士，他是京爷团队的高级助理，专注于图算法、优化与数据结构。

Maximilian Probst

此外，这项研究还有两位华人作者，分别来自卡内基梅隆大学的Li Chen和普林斯顿大学的Yang P. Liu。

如果您对这项研究感兴趣，可以通过下方链接深入了解。

参考链接

[1] ETH Zurich官方报道：https://ethz.ch/en/news-and-events/eth-news/news/2024/06/researchers-at-eth-zurich-develop-the-fastest-possible-flow-algorithm.html

[2] ACM论文：https://dl.acm.org/doi/10.1145/3618260.3649745

[3] Hacker News讨论：https://news.ycombinator.com/item?id=40829459

[4] ETH计算机系新闻：https://inf.ethz.ch/news-and-events/spotlights/infk-news-channel/2023/07/frontiers-of-science-awards-for-rasmus-kyng-and-maximilian-probst.html