AnChiang's Note: Noise is a Good Thing

最近想養成瀏覽 paper 就像看報紙一樣的輕鬆自在的習慣，早上挑選了 1970 年 B.W. Kernighan and S. Lin 的 An efficient Heuristic Procedure for Partitioning Graphs. 這篇文章吸引我的是他被引用次數高達 2618 篇。在第一頁中，提到了 Maximum flow Network 的 Ford and Fulkerson ，心中閃了個雜念，來查一下這兩人的背景。

在 Fulkerson 中看到有個 Fulkerson Prize ，這是由 MPS 和 AMS 每三年一次，挑選在離散數學及計算理論的重大貢獻。

最近一次於 2009 共頒了三給了三項結果，一為圖論的 Perfect Graphs Theory ，另一為計算幾何的 Sphere Packings, V. Pentahedral Prisms ，而吸引我注意的則是 D. A. Spielman and S.-H. Teng, "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time" , Journal of ACM 51 (2004) 385-463

Simplex algorithm 是一個在 Linear Programming 中，相當實用的演算法。在 wikipedia 上可以看到如下的描述：

The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the century.^[1]

Simplex algorithm 在實務上有相當好的效率，但在理論上有個缺點，就是存在些獨特的例子，使得其 running time 會到 exponential 的 scale 。後來 average running time 的 analysis 提出後，Simplex algorithm 也被證明其 average running time 是 polynomial 的。對大部份的人來說，這個解釋就足以說服他有相當好的執行效率。

但 A. Spielman and S.-H. Teng 就是對這解釋然有不滿，雖然 average 是 polynomial ，可是卻鮮少有些自然的情況會讓他有 exponential 的 running time。這之間，一定還有更大的學問。於是他們便提出 Smoothed Analysis ，來解釋這現象。

引用A. Spielman and S.-H. Teng 在 ICM 2002 給的介紹，可以看出Smoothed Analysis 想要去評估：對任意一個 instance ，

想去了解這 instance 和其相近的 instance 的 average running time 。而在去分析所有 instance 的 average running time 的 worst case。

於是 A. Spielman and S.-H. Teng 便說 simplex algorithm 在 smoothed analysis 下有 polynomial time 的 performance。這就說明了除非是刻意製造的完美反例，才會導致 exponential 的 running time，當這完美反例，在多了一些干擾，反而可以在 polynomial time 的時間完成，於是有 noise 反而卻成了一件好處。