2012年5月5日 星期六


Satish Rao, 有幾篇 graph partitioning 的相關研究。


張貼者： 於 沒有留言:
標籤：

2012年5月4日 星期五

Oded Shmueli


An algorithm for partitioning trees augmented with sibling edges
張貼者： 於 沒有留言:
標籤：

Rajesh Bordawekar


主要是因為他在Tree partitioning 的文章，才看到他的。





在 IBM 工作，發表文章數蠻多的。










張貼者： 於 沒有留言:
標籤：

Bordawekar and Shmueli [2008, IPL] An algorithm for partitioning trees augmented with sibling edges



這篇主要提到的是  partitioning with with sibling edges。






partitioning ：確保每一塊的大小上限，切出最小塊。







但這篇的 sibling edges 是有 order 的。因此他仍可以在 linear time 的時間做到。













張貼者： 於 沒有留言:
標籤： ,

2010年4月6日 星期二

走出去，才會躍出那山丘頂。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 的方法，可說是來自於 \lambda-Opt 的想法。當一個解處於 \lambda-Opt 是指任意調換 \lambda 個點後，並無法得到更好的解。這\lambda-Opt 之解，可以視為一個 local optimal 之解，當 \lambda 大至整個 set ，其 local optimal 之解才成為 global optimal。但因隨著 \lambda的增大，其時間也是指數次的成長，因此多數演算法也只是考慮 \lambda 為 1,2 的情況。

Kernighan  & Lin 改進了 \lambda-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 最佳解的機會提高不少。 

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



















張貼者： 於 沒有留言:

2010年3月20日 星期六

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


設 s_1,s_2,\dots,s_n 為依大小排序後的序列，在 quick sort algorithm 中，當 s_i 被挑選為 pivot 時，若 s_j 和 s_i 有比較大小，則定令 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 中，







張貼者： 於 沒有留言:

2010年3月5日 星期五

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。
























張貼者： 於 沒有留言:
訂閱： 意見 (Atom)