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 最佳解的機會提高不少。
以這哲理來說，就是多走出去看看，就有更大機會遇到更好的解，才不會只安於局部的最佳情況。
