無(wú)向圖最小割問(wèn)題取得新突破，谷歌研究獲SODA 2024最佳論文獎(jiǎng)

AIGC動(dòng)態(tài)歡迎閱讀

原標(biāo)題：無(wú)向圖最小割問(wèn)題取得新突破，谷歌研究獲SODA 2024最佳論文獎(jiǎng)
關(guān)鍵字：最小,算法,線性,時(shí)間,權(quán)重
文章來(lái)源：機(jī)器之心
內(nèi)容字?jǐn)?shù)：5390字

內(nèi)容摘要：

機(jī)器之心報(bào)道
機(jī)器之心編輯部谷歌博客放出新研究，求解無(wú)向圖的最小割問(wèn)題。1996 年， 美國(guó)計(jì)算機(jī)科學(xué)家 David R Karger 連同其他研究者在論文《 A new approach to the minimum cut problem》中提出了一個(gè)令人驚訝的隨機(jī)算法 Karger 算法，其在理論計(jì)算機(jī)科學(xué)中非常重要，尤其適用于大規(guī)模圖的近似最小割問(wèn)題。
Karger 算法可以在時(shí)間為 O (m log^3n) 的圖中找到一個(gè)最小割點(diǎn)，他們將這個(gè)時(shí)間稱之為近線性時(shí)間，意思是線性乘以一個(gè)多對(duì)數(shù)因子。
在谷歌剛剛更新的一篇博客中，他們介紹了之前發(fā)布的一篇論文《 Deterministic Near-Linear Time Minimum Cut in Weighted Graphs 》，研究獲得了 ACM-SIAM SODA24 最佳論文獎(jiǎng)。文章詳細(xì)闡述了一個(gè)幾乎是線性時(shí)間內(nèi)（而不是近線性時(shí)間）運(yùn)行的新算法，這個(gè)算法是確定性的，能夠可靠地找到正確的最小割，改進(jìn)了之前可能無(wú)法保證結(jié)果正確或只適用于簡(jiǎn)單圖的算法。可以說(shuō)這是自 Karger 著名的隨機(jī)化算法以來(lái)的重大發(fā)現(xiàn)。論文地址：htt

原文鏈接：無(wú)向圖最小割問(wèn)題取得新突破，谷歌研究獲SODA 2024最佳論文獎(jiǎng)

聯(lián)系作者

文章來(lái)源：機(jī)器之心
作者微信：almosthuman2014
作者簡(jiǎn)介：專業(yè)的人工智能媒體和產(chǎn)業(yè)服務(wù)平臺(tái)