頂點覆蓋的 2 近似（2-approximation for vertex cover）

一張圖的頂點覆蓋是一組頂點，碰到每一條邊——挑出一些人（頂點），使每段友誼（邊）的兩個端點至少有一個被選中。找出「最小」的這種集合是 NP 困難的。然而有一個出了名簡單的演算法，永遠不會把最佳值超過兩倍，而它正是「近似保證如何被證明」最乾淨的範例之一。

整個演算法如下。重複直到沒有邊剩下：任選一條尚未覆蓋的邊 (u, v)，把「兩個」端點 u 和 v 都加進你的覆蓋，再刪掉所有碰到 u 或 v 的邊。你一次一條挑出的這些邊互不共用端點——它們構成所謂的匹配，事實上是極大匹配。為何結果是合法覆蓋？你刪掉的每條邊都被 u 或 v 碰到，所以都被覆蓋；迴圈只在所有邊都消失時才停，所以每條邊都被覆蓋。為何最多是最佳值的 2 倍？設你挑了 k 條邊，你的覆蓋就有 2k 個頂點。這 k 條邊互不共用端點，所以「任何」覆蓋——包括最佳覆蓋——都必須在每條邊上各花一個相異頂點：OPT >= k。因此你的 2k 最多是 2 * OPT。這一個比較，你的覆蓋對上匹配大小，就是整個證明。

這裡的妙處在於：匹配大小 k 是你算得出來的量，而它同時又是 OPT 的可證下界——正是讓近似證明在不知道 OPT 的情況下仍能成立的那個替身技巧。誠實的限制：兩個端點都拿是浪費的（在真實圖上更聰明的選法也許用更少頂點就覆蓋了同樣的邊），而因子 2 基本上是已知最佳的簡單組合界。要大幅做得更好很難：在一個被廣泛相信的猜想（唯一賽局猜想）下，沒有多項式演算法能把 2 改進任何常數，所以這個樸素方法在某種精確意義上已近乎最佳。