ACM-SIAM SODA24 - AI在线

无向图最小割问题取得新突破，谷歌研究获SODA 2024最佳论文奖

谷歌博客放出新研究，求解无向图的最小割问题。1996 年，美国计算机科学家 David R Karger 连同其他研究者在论文《 A new approach to the minimum cut problem》中提出了一个令人惊讶的随机算法 Karger 算法，其在理论计算机科学中非常重要，尤其适用于大规模图的近似最小割问题。Karger 算法可以在时间为 O (m log^3n) 的图中找到一个最小割点，他们将这个时间称之为近线性时间，意思是线性乘以一个多对数因子。在谷歌刚刚更新的一篇博客中，他们介绍了之前