走出去，才會躍出那山丘頂。Note For ST_1969_An Efficient Heuristic Procedure Fo

2642的引用次數，是吸引我看 Kernighan 這篇文章的原因。這是目前所讀的 paper 內引用次數最多，且年份也是最古老的。

在 Kernighan & Lin 這篇所討論 graph partition 問題起源於電路板或程式的分頁儲存問題。

在給定每個分頁的上限下去 partitiotn ，使得那些跨越不同 partitions 的 edge 越少越好。

以上例來說當partition成 {v2,v3,v5}  {v1,v4,v6} 兩組時，則要 remove 掉紅色的邊，其 cost 為 16。在此關心的問題是如何讓這些 remove edges 的 total cost 達到最小

Remark1: 上圖為一個最佳解)。

Remark2: 度量最小的 remove edge ，也等價於計算保留在同個 partitiong內的邊數的最大 weight之和 ，在 {v2,v3,v5} 內為 9+5, 在 {v1,v4,v6} 內為 4+5。

 

Kernighan  & Lin 的方法，可說是來自於 -Opt 的想法。當一個解處於 -Opt 是指任意調換  個點後，並無法得到更好的解。這-Opt 之解，可以視為一個 local optimal 之解，當  大至整個 set ，其 local optimal 之解才成為 global optimal。但因隨著 的增大，其時間也是指數次的成長，因此多數演算法也只是考慮  為 1,2 的情況。

Kernighan  & Lin 改進了 -Opt 之想法，使其在變換過程， hit 到 global optimal 的機會提高。

對於 A,B 兩個 partitioning set ，他要把 A, B 兩個集合完全調換。對於 partitioning 來說，雖然完全調換後其 cost 仍不變，但他想要去找尋在這調換的過程中，是否有機會出現更好的解。

調換的過程為對於任一尚未調換後的點，每次選取兩點，使其調換後的狀態最佳(ps: 也可有能調換後變差，但仍繼續調換)，直到 A,B 兩個集合完全對調。若這過程有出現比 (A,B) 更好的解(A',B')，則下次在從(A',B') 調換至 (B',A') 直到調換過程沒有出現更好的解。

以這個示意圖來描述一下 Kernighan  & Lin 的想法，一開始從 a 點出發，每次挑選最佳的情況走出去一圈又繞回來。若 b 為這一圈最高點，則下次從 b 出發。值得注意的是一般的 heursitic 方法，可能是當 從 a 出發，若 a 的鄰點狀況都比 a 還糟，則就停在 a 這點。但在 Kernighan   & Lin 繼續往外走，說不定在多走幾步就會遇到更好的。整個過程重複到，從 c 出發走一圈，遇到最好的 d，但從 d 點出發後，走一圈都沒更好的，此時才結束。這方法試圖在不過度增加搜尋的時間下，使得 hit 到 global 最佳解的機會提高不少。 

以這哲理來說，就是多走出去看看，就有更大機會遇到更好的解，才不會只安於局部的最佳情況。

Note for Smoothed Analysis of Three Combinatorial Problems

上週初看 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 下，要去估計任兩個元素的比較次數。

設  為依大小排序後的序列，在 quick sort algorithm 中，當  被挑選為 pivot 時，若  和  有比較大小，則定令  為 1，若無則為 0。

對於average analysis 即為，當 p = 1 時，則 期望值為  ，於是   。

當 p <1 時，對於   之值的估計要作比較仔細的分析。主要想法分為若  有機會變為很靠近的點則視其值為 1，且論證此類情形不太多。而對其他大多數情況，則因其距離較遠，可論證其   會比較的機率較小。因此評估起來其期望值為 。

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

在此文的後半部在討論 left-to-right-maxima 問題，其想要陳述的為原先的 worst case instance ，在 smoothed analysis 後，並不一定為 worst case ，以及其 recursive depth 不為 。而在最後的 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 中，

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 反而卻成了一件好處。

而 A. Spielman and S.-H. Teng 的觀察不只讓他們得到  Fulkerson Prize ，也讓他們得到2008 的 Gödel Prize。

另外在引用一篇其他人寫得介紹 http://behind-the-enemy-lines.blogspot.com/2009/10/when-noise-is-your-friend-smoothed.html

KSplit Note's

最近想認真作些研究，但卻又缺乏那麼一點動起來的衝勁。

做個沒人知道的研究，就常會懷疑自己到底在些什麼，該不該往下繼續做呢？通常想到這，就連動手都還沒動，就宣告放棄了，於是研究就一直停滯不前。

我想來寫寫研究日記，想像有人在關心，這樣我就會更熱衷於書寫更熱衷於研究？

這兩三天重看了一年前發現的 ksplit 小結果。這結果是在看完 Perl 的 max-min  tree partition 的 shift Algorithm 後，才發覺我原先引以為傲的 Evol-and-Eval 解法還不如 shift 來的簡潔。

這兩天原本想開始把這想法重新書寫下來。但今早在重看一下，只要作個轉換，把 tree edge 的 k-split 問題， 轉換成 binary tree ，而直接在 binary tree 上套用 shift algorithm 就可以得到 ratio 2 的解法。

看看今天能否把這想法用 latex 寫個初稿。

Notes For K_1971_JACM_Optimal Sequential Partitions of Graphs

在 2000s 年的 partitions 問題，關心的是 XML tree 上的儲存， 而 1970s 上的 partitions 則是關注於 Programs 的儲存。

在眾多 Reference 中，撇見一篇 1971 JACM 的 Optimal Sequential Partitions of Graphs， 腦中還在想這麼老舊的文章是否有研讀的必要。

看在其為 JACM 的份上，便在 Google Scholar 輸入關鍵字，出現 82 篇引用，以 JACM 的文章這種引用數或許不算多。

但或許是標題已標明了 "optimal" 一詞 ，後續也不太有改進的空間。

DBLP 內雖只有 28 筆資料，但在 google 輸入 Brian W. Kernighan ，第一筆不是作者的個人網頁，而是 wikipedia 頁面，而下方的圖片搜尋，還出現一個熟悉的照片。

這個蓋著 ANSI C  的印章的書，不就是我五年前修習單維章教授所開設程式設計的教科書，我的 C 語言啓蒙書。這...這就是傳說中的C語言經典 K & R 。原來 Kernighan 就是其中的 K。

很快速地翻閱了這篇僅有 7 頁的 Optimal Sequential Partitions of Graphs, 整篇也只是用到了 Dynamic Programming 並沒有用到太複雜的概念。我當初還在想是不是因為 Kernighan 的名氣讓這篇被接受。

查完 DBLP 資料，竟發現這篇 “Optimal Sequential Partitions of Graphs” 是 Kernighan 在 DBLP 的第一筆資料。細查其他文獻，看到 1969 年有篇 Ph.D Thesis 其作者就是 Kernighan  ，也就是這篇 JACM 的文章其實就是 Kernighan 博士論文的一個結果。所以拿 Partition Problem 來當 Ph. D Thesis 或許是件很值得驕傲的事吧。

我以下圖，來解釋 Kernighan 在這篇考慮的 partition 。因其考慮的是 programs 的 partitioning,  因此 graphs 的每個 vertices 有其自然的順序，在 partition 時，每個 partition 只能包含一段連續的 vertices 。而其邊上的 weight 表示這兩個 vertices 會相互呼叫的頻率。因此每個 partitions 給定其大小上限(下列為 4)，要找一個切割方式，使得那些跨 partitions 的 edges 之 weight 總和越小越好。

在上述的圖示中，可窺探其實只用到了 Dynamic Programming 的概念，而在 Theorem 4 證其 running time 也只是 O(E) 。在這篇中，除了 Theorem1 證明了這是 optimal 的解外，他也論證 (Theorem 2) 此方法會得到在所有 optimal solutions 中， partitions 的個數是最小的。在 Theorem 3 論證了 partitions 的個數也不會太大( expansion factor <2)。最特別的是其 Theorem 5 的敘述，不可能存在一個方法，只靠 local information 就能決定 cut edge 要在哪邊。

整體來看，這篇文章論述是很完整，但手法概念上其實不算難懂，能上 JACM 或許是這問題在當時有其重要性？

How do you Measure a Year?

一年內要看完 100 篇 paper。