最大流的最新演算法，複雜度低至O(VE)，有實際應用價值嗎？為何很少見人提到？

01-08

Orlin"s algorithm solves max-flow in O(VE) time for
while KRT solves it in O(VE) for

以下是JAMES B. ORLIN的論文「Max flows in O(nm) time or better.」
MIT Sloan Faculty
以下是最大流的維基頁面
Maximum flow problem

理論上來說有用: 看起來 $O(mn)$ 就漂亮了許多. 雖然我們現在感覺可能並不是真lower bound. (現在唯一的lower bound是 $Omega(m)$ , 一個很大的open problem能不能做的更好.)

實用上來說, 很久以前就有 $O(mnlog n)$ 級別的演算法了啊. 這個 $log n$ 實際上沒多少意義的. 而且那也沒有人用因為要用到dynamic tree.

而且現在有near linear time的approximation algorithm. 對於很多問題來說得到(1-epsilon)-approximation就夠用了.

我最近看到一個人cite orlin的文章, 但是裡面東西的capacity都蠻小的, 於是表明還不如用Goldberg-Rao.

最近投的論文正好引了這個結論。

大概就是對於某個NP-Hard的問題，之前有人提了一個用網路流的近似演算法，然後我們想了另一個，近似比是一樣的。

我一開始以為網路流最快的演算法是演算法導論上的O(V^3)，所以算了一通告訴老闆我們的演算法比他快。後來查到這個之後才發現只有在V和E滿足一定關係的時候才快，真是個悲傷的故事……

【幸好這隻能算文章中的一個小部分

不過個人感覺這個演算法的理論價值可能更大一些。最明顯的，其實它需要結合另一個演算法一起（差不多是分E=O(V)和E=omega(V)的情況）才能確保O(VE)的時間複雜度。我覺得實際應用中搞個這種寫法是件挺蛋疼的事情……

拋磚引玉，坐等更有乾貨的答案~

這時候應該祭出 Yin Tat Lee 神牛，香港人，在 MIT 讀 PhD，這個秋天在 UCB Simons 交換（似乎並沒有 -_-b 今天看到他了 Nov 5），有興趣的同學趕緊套磁。

他和 Aaron Sidford 在 FOCS 2014 上扔了兩枚重磅炸彈 http://arxiv.org/abs/1312.6677http://arxiv.org/abs/1312.6713 首次提供了運行時間為 $ilde O(msqrt n)$ 的最大流演算法。

在 Yin Tat Lee 大神這篇 paper 前 15 年，也有 $ilde O(m n^{2/3})$ 的演算法（by Goldberg and Rao）。

不過這兩個演算法的時間複雜度都含有 $log U$ ，是一個和精度有關的項。例如，如果每條邊的最大流量都是一個小整數，那 $log U = O(log m)$ 可以忽略不計。這時 Yin Tat Lee 暴打 Orlin"s algorithm。但如果邊上的流量可以是任意大的整數或精度很高的實數，而且還要求得出精確解，那 Yin Tat Lee （和 Goldberg and Rao）的演算法就要吃虧。這時就有 Orlin"s algorithm 的出頭之日了。

演算法研究在計算機領域算是比較基礎的領域了，研究的目標當然不只是解決某個應用問題，而是在現有框架下明確盡量多的結論和可能性。

不過既然要提用途的話，最大流在圖像分割方面要比傳統的機器學習演算法效果好很多。另外機器翻譯也常常要做多詞之間的匹配，一般的匹配演算法只能做1對1的匹配，所以有時會用網路流來做，而字典往往是10^4及以上，一個實驗跑上幾天是常事，所以演算法上但凡有點提升都對實際應用會有些幫助，另外，沒準以後在這個演算法基礎上會有新演算法提出能更高效的解決一些特定問題。

這個演算法需要用到斐波那契堆。不實用。