AnChiang's Note: 3月 2010

上週初看 Spielman, Teng 的 Smoothed Analysis 的觀點，感到有些驚奇，本來也想從原始論文 simplex method 那方面直接切入，

刊載在 JACM 的原文長達 80 頁，另有幾篇Spielman, Teng 在 STOC2001, ICM2002, CACM 2008 的介紹文章，只是稍微看懂 introduction 的介紹。

問題都還是環繞在 linear programming 上，但也還沒那麼多心力去了解 linear programming 的細節。

最後還是先以熟悉的 combinatorial Problems 來作個對 smoothed analysis 的初步探究。
在 Banderier Mehlhorn, Beir 這篇文章裡討論了三個問題 quick sort, left-to-right Maxima, single source shortest Path Problems.

今天則先 focus 在 quick sort 這問題上。

首先從 smoothed analysis 的式子來了解，可看出smoothed analysis 是個介於 worst case analysis 和 average case analysis 之間的分析。smoothed analysis 是對於每一點，採其 neighbor 作平均。接著才在對這些平均中取其 worst case。當這 neighbor 小至只有一點時，即為 worst case analysis ，若 neighbor 大至全部，則為 average case analysis。

以下兩示意圖對來對於上述式子來在觀察哪些情況是適用於 smoothed analysis。藍色的曲線為每個 instance 的 running time，

綠色的曲線為 average case 的 running time。紅橘兩曲線則各取附近5點, 10 點的平均 running time。

若某演算法對其中有些 worst case 都很集中，則 smoothed analysis 後，也沒有太好的表現。

但若那些 worst case 很稀很分散，則 smoothed analysis 則有比較好的表現。

這也就是為何 smoothed analysis 可用來解釋 algorithm 在“實際應用”上的表現。現實世界的資料是充滿很多干擾、雜訊。因此若演算法的的表現如圖二，則實際執行時，會掉入那些稀有的 worst case 的機率其實不高。

但問題是如何定義“擾動”呢？在 quick sort 中，採用 partial permutation 的方法。每元素有 p 的機率會改變其位置，也就是平均有 np 的元素會改變，對於這些會被改變的 m 個元素，其有 m! 種置換方式。

基於這 partial permutation 的 models 下，要去估計任兩個元素的比較次數。

設 $s_1,s_2,\dots,s_n$ 為依大小排序後的序列，在 quick sort algorithm 中，當 s_i

被挑選為 pivot 時，若 s_j

和

有比較大小，則定令 $X_{i,j}$ 為 1，若無則為 0。

對於average analysis 即為，當 p = 1 時，則 $X_{i,j}$ 期望值為 $\frac{1}{|i-j+1|}$ ，於是 $\sum_i\sum_j \frac{1}{|i-j+1|} = O(\log{n})$ 。

當 p <1 時，對於 $X_{i,j}$ 之值的估計要作比較仔細的分析。主要想法分為若 s_i,s_j

有機會變為很靠近的點則視其值為 1，且論證此類情形不太多。而對其他大多數情況，則因其距離較遠，可論證其 s_i,s_j

會比較的機率較小。因此評估起來其期望值為 $O(\frac{n}{p}\log{n})$ 。

對於細部的分析，則有以下的 7 cases:

在此文的後半部在討論 left-to-right-maxima 問題，其想要陳述的為原先的 worst case instance ，在 smoothed analysis 後，並不一定為 worst case ，以及其 recursive depth 不為 $O(\frac{1}{p}\log{n})$ 。而在最後的 single shortest path problem ，則討論另一種擾動的 model : "partial Bit Randomization".

對於怎樣才是個合適的"擾動"也是個蠻重要的問題。例如，當我們看一個 maximum clique 的問題，所予許的小擾動是每個vertex pair 的連結有 p 的機會會改變，這樣便很容易破獲原本 maximum clique 的 property。如何來要在維持 property 的情況下，再去討論擾動的狀況， Spielman, Teng 在

Smoothed Analysis: Motivation and Discrete Models 中，也對其做了些相關討論。

在 smoothed analysis 中，

最近想養成瀏覽 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 反而卻成了一件好處。