兩個新念頭，一個老目標
在這一階到目前為止，你的近似解都是手工掙來的：一個巧妙的極大匹配技巧給了你 頂點覆蓋的 2-近似，一個貪婪的對數給了你 集合覆蓋的保證，一棵生成樹給了你 度量 TSP。每一個都是一次性的靈光。這一篇用一套方法取代靈感，這方法一次就適用於一大族問題。計畫恰好兩步：先鬆弛，再捨入。
起點的觀察是：幾乎每個組合問題都能寫成一個整數規劃（IP）：為每個物件決定一個 0/1 的值——納入這個頂點與否、選這個集合與否——在線性約束之下，最小化一個線性成本。頂點覆蓋是最乾淨的例子。給每個頂點 v 一個變數 x_v，它必須是 0 或 1。目標是最小化所有頂點上 x_v 的總和（覆蓋的大小）。約束是：對每條邊 (u,v)，至少有一個端點被選中：x_u + x_v >= 1。那個 IP 是最小頂點覆蓋的一個精確描述——但解整數規劃一般而言是 NP 困難的，所以我們只是把困難搬了個地方，並沒有移除它。
minimize sum over v of x_v (cover size)
subject to x_u + x_v >= 1 for each edge (u,v)
x_v in {0,1} <-- IP: NP-hard
0 <= x_v <= 1 <-- LP relaxation: poly-time鬆弛：從難解的整數到好解的區間
鬆弛這一步簡單到近乎令人不好意思。把要求 `x_v in {0,1}` 換成要求 `0 <= x_v <= 1`。現在每個變數可以取那段區間裡的任何實數——一個頂點可以有 0.5 在覆蓋裡。這就是 線性規劃鬆弛：一個 線性規劃，在連續變數的線性不等式上最小化一個線性目標。關鍵事實是：與它的整數母題不同，線性規劃可在多項式時間內解出（實務上用單純形法，在可證明的多項式時間上用內點法或橢球法）。
這裡是第一個承重的觀察，而它對你用這種方式鬆弛的每個最小化問題都成立。每一個整數解也是一個分數解——整數 0 與 1 住在區間 [0,1] 裡面。所以 LP 是從一個嚴格更大的選項集合裡挑選，比 IP 的更大。一個能搜尋更大可行域的最小化者，只可能做得至少一樣好。因此 OPT_LP <= OPT_IP = OPT：LP 的最佳值是真正最佳值的一個下界。這一條不等式就是整個方法能行的全部理由——它給了我們一個具體的東西，來衡量我們捨入後的解。
捨入，展品一：用門檻法做頂點覆蓋
解出 LP，你會得到一個最佳的分數向量 x*，每個 x*_v 落在 [0,1] 裡的某處。我們需要一個真正的覆蓋，所以對每個頂點必須做決定：進還是出。門檻捨入規則殘酷地簡單——若 x*_v >= 1/2 就把 x*_v 進位到 1，否則捨去為 0。有兩件事必須查驗，而它們恰好就是任何捨入證明都需要的那兩件：結果是可行的（一個合法的覆蓋），而它的成本不會比 OPT_LP 高出太多。
- 可行性。任取一條邊 (u,v)。LP 約束逼出 x*_u + x*_v >= 1，所以這兩個值不可能都低於 1/2（兩個小於 1/2 的數相加會小於 1）。因此至少一個端點的值 >= 1/2，於是被進位到 1。每條邊都保住了一個被選中的端點，所以捨入後的集合是一個合法的頂點覆蓋。
- 成本。每個變數被進位的倍率至多是 2：若它存活，x*_v >= 1/2，所以 1 <= 2 * x*_v。對整個覆蓋求和，它的大小至多是 2 * (x*_v 的總和) = 2 * OPT_LP。
- 接回 OPT。既然 OPT_LP <= OPT，捨入後的覆蓋大小至多是 2 * OPT_LP <= 2 * OPT。這就是一個 2 倍的保證：一個多項式時間的演算法，永不回傳大於最佳值兩倍的覆蓋。
停一下，想想剛剛發生了什麼。我們取回了與第二篇裡極大匹配論證相同的 近似比 2——但靠的是一套完全機械、從未提到匹配的食譜。那個聰明的組合洞見，被「寫出 IP、鬆弛、門檻捨入」給取代了。這才是真正的回報：不是這裡有更好的比值，而是一條系統化的路徑，你可以把它對準下一個、再下一個問題，那些身邊並沒有現成聰明洞見的問題。
捨入，展品二：集合覆蓋的隨機捨入
門檻捨入之所以管用，是因為每條約束只有兩個變數，所以保證有一個很大。大多數問題沒這麼好心。集合覆蓋有像「元素 e 被某個被選中的集合覆蓋」這樣的約束，而一個元素可能落在數十個集合裡，每個都只有一丁點的分數值——沒有任何單獨一個跨過 1/2。解方是擲硬幣。在隨機捨入裡，我們把每個分數值 x*_S 當成一個機率：以機率 x*_S，獨立地把集合 S 選進我們的解。這是整個主題裡最優雅的念頭之一。
又是兩個問題：成本與可行性。期望成本既簡單又漂亮：由期望值的線性性質，期望的總成本是所有集合的 (S 的成本) 乘上 (機率 x*_S) 的總和——這恰好就是 LP 的目標值 OPT_LP。所以平均而言，一輪擲硬幣的花費不超過下界本身。可行性是微妙的部分：單獨一輪可能因為運氣不好而留下某些元素未被覆蓋。對一個落在「分數值總和至少為 1」的那些集合裡的元素 e，它被全部漏掉的機率至多是 1/e（自然對數的底）——也就是說被覆蓋的機率超過一半（至少約 1 - 1/e），但仍不是保證。
解法是重複。把隨機捨入獨立地跑大約 c * ln(n) 次，取所有曾被選中的集合的聯集，其中 n 是元素的數目。一個固定元素在這麼多輪之後仍被漏掉的機率，降到大約 (1/e)^(c ln n) = n^(-c)，於是對全部 n 個元素做一次聯集界，就讓任何元素被漏掉的機率消失。成本以同一個 ln(n) 因子增長，給出一個 O(log n)-近似——與第二篇的貪婪保證相符，但如今是從 LP 得來的。誠實查驗：這是一個 隨機演算法，所以它的保證是關於期望值與高機率的，而非對每一次執行都鐵板釘釘的承諾；特別倒楣的一次執行可能更差。
下界能有多好？整數性間隙
上面的一切都懸在一個我們應該正眼看待的數字上。LP 給了一個下界 OPT_LP，但它有多鬆——真正的最佳值跟分數的相比，能大到什麼地步？那個取遍所有實例的最壞情況比值，就是整數性間隙：OPT_IP / OPT_LP 能達到的最大值。它是這項技術的一道硬天花板。任何把自己的輸出拿來跟 OPT_LP 比的捨入方案，都永遠無法證明比整數性間隙更好的近似比，因為在最壞的實例上，連最佳的整數解都比你拿來衡量的那個下界大上這麼多倍。
一個生動的例子是三角形：三個頂點、三條邊。把每個 x_v 設成 1/2，就滿足了每條邊的約束（1/2 + 1/2 = 1），分數成本是 3/2。但任何三角形的整數覆蓋都需要 2 個頂點。所以這裡 OPT_IP / OPT_LP = 2 / 1.5 = 4/3，而人們可以把一族族的圖推向頂點覆蓋的整數性間隙 2。這正是為什麼我們的門檻捨入停在 2 倍、且透過這個 LP 無法做得更好——下界本身就最多差了 2 倍，所以沒有任何捨入能擠過它。整數性間隙不是聰明才智的失敗；它是這個鬆弛的一個性質。
第二具引擎，以及整套路數的界限
把 LP 解到精確有時是殺雞用牛刀，而有一個表親方法常常乾脆跳過它。原始對偶法同時操作 LP 與它的對偶：它長出一個可行的對偶解（由 LP 對偶性，這本身就是 OPT 的一個下界），並用對偶解以組合的方式決定要把什麼放進原始的整數解。做對了，它產出相同的 2 倍頂點覆蓋與相同的 O(log n) 集合覆蓋——但作為一個快速、往往純組合、從不呼叫 LP 求解器的演算法。它是同一個「下界加捨入」的念頭穿上了工作服；原始對偶法 是實務中許多最快的近似演算法背後的引擎。
現在是你必須尊重的界線。鬆弛加捨入很強大，但它不是一把打開每道門的萬能鑰匙。你能證明的品質，由整數性間隙從下方框住，而那個間隙有時糟透了：對一般的集合覆蓋，間隙是 Theta(log n)，所以 LP 根本無法保證比一個對數因子更好的東西——而了不起的是，複雜度理論說，除非 P = NP，否則沒有多項式演算法能本質上做得更好。對某些問題，自然的 LP 有一個無界的間隙，不加強就毫無用處。這個教訓呼應了整一階：一個鬆弛是一件有著已知觸及範圍的工具，而善用它的一部分，是在你開始捨入之前，就知道那個下界究竟能帶你到多遠。