迄今最快的网络流算法，网友：几乎与数学理论一样快

十三 2024-06-30 14:00:04 来源：量子位

金磊 发自 凹非寺

量子位 | 公众号 QbitAI

迄今为止最快、近乎完美的网络流（Network Flow）算法，来了！

有多快？

对于任何类型的网络，计算速度几乎与数学理论一样快。

而且还是以最低成本计算最大运输流量的那种。

这就是来自苏黎世联邦理工学院计算机系Rasmus Kyng（下文简称“京爷”）团队最新研究：

其实早在两年前，京爷团队所做的“前代”研究就已经在圈内走红，曾被Quanta Magazine评为当年的计算机科学十大发现之一。

网络流算法先驱Daniel A. Spielman也给出了相当高的评价：

快得离谱，像保时捷超跑一样。

而就在最近，他们在ACM计算理论研讨会（STOC）中带来了“进化版”研究——

不论是网络里增加或删除了什么路径，依旧能够以最低成本、最大传输流量的“姿势”，用几乎线性的速度进行计算。

就好比徒步旅行一样，管你道路变多了还是变陡峭了，我依旧保持高速前行、顺利抵达终点。

苏黎世联邦理工学院官方给出的评价是：

超快算法为未来高效计算超大型动态变化的网络奠定了基础，有望改变整个研究领域。

那么京爷的团队又是如何做到这一点的呢？

迄今最快的网络流算法

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

这个问题早在1955年，由T.E.哈里斯在研究铁路最大通量时，为了寻求两点间最大运输量而被提出。

在1956年，L.R.福特和D.R.富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。

并且网络流算法在解决现实问题时有很大的应用价值。

例如你在使用欧洲运输网络的时候，希望寻找最快、最便宜的路线，将尽可能多的货物从哥本哈根运送到米兰，这时候网络流算法就能发挥作用了。

对于这个问题，以前计算最佳流量所需的时间甚至比处理网络数据的时间要长得多。

而随着网络变得越来越大，越来越复杂，相对而言，所需的计算时间比计算问题的实际规模增长得快得多。

这也就是为什么我们还能看到计算机有时都无法对网络中的流量进行计算的原因。

但京爷团队所提出的算法，就一举打破了这一局面——

不仅读取网络数据到解决方案所需的“额外”计算时间现在可以忽略不计，即便是重新设计路由（Route）还是添加新路由，都可以忽略不计。

原则上，所有计算方法都面临着必须多次迭代分析网络的挑战，以此来找到最佳流量和最低成本路线。

在京爷团队之前，研究人员倾向于在两种关键策略之间做选择：

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

京爷团队的做法则是——成年人不做选择题，二者的优势统统都要，组合打造新方法：

我们的方法基于许多小的、高效的和低成本的计算步骤，这些步骤加在一起比几个大的计算步骤要快得多。

这在开发几乎线性时间算法方面发挥了关键作用。

最新的这项研究，提出了一系列针对增量图（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

除此之外，这项研究中还有两位华人作者，他们分别是来自CMU的Li Chen，以及普林斯顿的Yang P. Liu。

若是对这项研究感兴趣，可戳下方链接进一步了解。

参考链接：
[1]https://ethz.ch/en/news-and-events/eth-news/news/2024/06/researchers-at-eth-zurich-develop-the-fastest-possible-flow-algorithm.html
[2]https://dl.acm.org/doi/10.1145/3618260.3649745
[3]https://news.ycombinator.com/item?id=40829459
[4]https://inf.ethz.ch/news-and-events/spotlights/infk-news-channel/2023/07/frontiers-of-science-awards-for-rasmus-kyng-and-maximilian-probst.html