假設現在有一個地下水管道網絡，現在自來水廠向網絡中輸水，你在一個點接水。由於管道修建的年代不同，不同管道能承受的水流量有大有小，那麼在自來水廠輸入的水不限的情況下，你一次能接到的水的最大值是多少？這就是計算機科學中最古老的問題之一——最大流問題，即從源點經過所有路逕到達匯點的所有流量和。
從1950年代開始，蘇聯的鐵路系統就開始研究最大流問題。「它可能比計算機科學的理論還要古老。」加州山景城谷歌研究中心的伊迪絲·科恩( Edith Cohen)說道。這個問題有很多應用：網際網路數據流、航空公司調度，甚至將求職者與空缺職位匹配。
從左上角順時針方向：Yang Liu、Li Chen、Rasmus Kyng、Maximilian Probst Gutenberg、Richard Peng和 Sushant Sachdeva
經過長久的努力，這個問題於近期出現了突破性進展——六位計算機科學家的新算法可在「幾乎線性」的時間內解決這個問題，這意味著該算法的運行時間大致與首次寫下該網絡細節所花費的時間相當。對於所有可能的網絡，解決這些問題的其他算法都無法達到如此快的速度。同時，這個新算法也處理了如何在最大流的同時最小化成本。
「簡直太棒了。」加州大學伯克利分校的Satish Rao表示，這個結果讓他跳了起來。
「現在我們知道我們可以非常快速地做到這一點，人們將會由此發現各種各樣他們以前沒有考慮過的應用程式。」耶魯大學Daniel Spielman表示。
目前，這主要是理論上的進步，因為速度提升只適用於遠大於我們在現實世界中會遇到的網絡。對於目前現實中會遇到的網絡，最大流量問題已經可以被相當快地解決（至少在不涉及最小化成本時候是的）。即使如此，該算法的六位創造者之一、加拿大滑鐵盧大學Richard Peng預測，新算法的某些部分可能也會在一年內得到實際應用。研究人員表示，在未來幾年，計算機科學家可能會找到使其更實用甚至更快的方法。
「即使確實出現了改進，這篇新論文也是『灌籃高手』。基本上是最好的。」麻省理工學院Aleksander Mądry說。
解決最大流問題的第一個算法一般追溯到1956年。當時Lester Ford和Delbert Fulkerson使用「貪婪」方法解決此問題，即在每一步都使用最容易獲得的對象。
想像一個運輸公司希望從洛杉磯向紐約一次性派出儘可能多的卡車。Ford和 Fulkerson的算法首先會選擇從洛杉磯到紐約的一條路徑，並沿該路徑安排儘可能多的卡車。但這通常不會利用該特定路徑上所有道路的全部容量，因為如果這個路徑的一部分是一條五車道高速公路，但它通向一座兩車道的橋樑，那麼在任何時候都只能一次安排兩輛卡車。
接下來，算法會修改這些路段的容量，從路段的容量中減去已安排的卡車數量。因此五車道高速公路現在只有容量3，雙車道橋的通行能力為零。同時，該算法在這些高速公路的反向容量上增加了2，因此如果需要，稍後可以撤消其中的一些流量。
然後，該算法會找到一條從洛杉磯到紐約的新路徑，沿該路徑發送儘可能多的卡車，並再次更新容量。經過有限數量的這些步驟，從洛杉磯到紐約的路徑將無法容納更多卡車，然後只需將所有流程組合起來，就得到一次最大可能安排的卡車數量。
在該算法發表後的幾十年裡，研究人員試圖通過讓算法做出更明智的選擇來加快運行時間。此後經過多次突破，這個運行時間再難低於m^1.33（Ford-Fulkerson算法是m^2），其中m是網絡中的連結數。
人們開始懷疑這個指數是不是一個基本極限。理論上，最大流算法的最快可能運行時間將是m（即m^1），因為僅僅寫下一個網絡就需要m步的倍數，這被稱為線性時間。但對許多研究人員來說，如此快速的算法似乎是不可想像的。
「沒有充分的理由相信我們可以做到這一點。」Spielman說。Mądry曾減少解決最大流問題所需的步驟數，但這種減少是有代價的：在每一步中，都必須重寫整個網絡，並從頭開始解決問題。
這篇新論文的六位研究人員想到一個新的思路，同時實現最小成本算法解決最大流量問題。想像一下，你創建了一條將卡車從芝加哥沿收費公路運送到紐約的流程，但隨後發現有一條更便宜的高速公路可用。增加從紐約開始的循環，沿著昂貴的道路運行到芝加哥，然後沿著更便宜的路線返回，這就有效地用更便宜的路逕取代昂貴的路徑，從而降低了總成本。
加拿大維多利亞大學Valerie King說，這種方法使用了更多步驟，「聽起來像是在倒退」。作為補償，算法在每一步都必須非常快地找到一個好的循環——這比檢查整個網絡更快。
這其中使用到了一種「低拉伸生成樹」（low-stretch spanning tree）新方法——一種捕獲網絡中許多最顯著特徵的內部主幹。給定這樣一棵樹，總可以通過從樹外部添加一個連接來構建至少一個良好的循環。因此，擁有低拉伸生成樹會大大減少需要考慮的周期數。
即使這樣，為了讓算法快速運行，團隊也無法在每一步都構建一個全新的生成樹。相反，他們必須確保每個新循環僅在生成樹中產生輕微的漣漪效應，以便他們可以重用之前的大部分計算。論文作者之一、史丹福大學研究生Yang P. Liu說，達到這種控制水平是「核心難點」。
最終，研究人員創建了一種在「幾乎線性」時間內運行的算法，這意味著在越來越大的網絡中，它的運行時間接近m。
