線性規劃捨入（LP rounding）

線性規劃鬆弛遞給你一個分數答案——變數停在 0.3、0.5、0.8 之類的值——但真實問題需要誠實的是非決定。線性規劃捨入就是把那些分數轉回合法 0/1 解的那一步，同時控制這次轉換要付的代價。技藝在於用某種方式捨入，使得 (a) 每個約束仍被滿足，且 (b) 成本相對 LP 最佳值的膨脹不超過一個可證的因子。

最乾淨的例子又是頂點覆蓋，而且它把因子 2 還了回來。解鬆弛；你得到分數值 x_i 屬於 [0, 1]。現在用一個簡單門檻捨入：當且僅當 x_i >= 1/2 時把頂點 i 放進覆蓋。第一，結果是合法覆蓋嗎？對任何邊 (i, j)，LP 保證 x_i + x_j >= 1，所以兩者至少一個 >= 1/2（不可能兩個都低於 1/2，否則和會小於 1）——因此至少一個端點被捨入上去，邊被覆蓋。第二，成本是多少？你捨入到 1 的每個變數本來就至少 1/2，所以捨入最多把它加倍：捨入後成本最多 2 * (x_i 之和) = 2 * LP-OPT。又因為 LP-OPT <= 整數-OPT，捨入後的覆蓋最多 2 * OPT。這是一個完整、自足、純由 LP 導出的 2 近似——不需要匹配。

這方法為何值得一席之地：它通用而有章法。你不需要像極大匹配那樣聰明的、問題專屬的把戲；你寫出 0/1 規劃、鬆弛它、用通用求解器解 LP、再用一條你能分析的規則捨入。同一套模板能為許多覆蓋與裝填問題給出近似。誠實的限制：不是每個問題都有一個既保持可行又給出好因子的門檻，所以捨入規則必須依問題設計；你能達到的品質從根本上被整數性差距封頂（若 LP 最佳值遠低於整數最佳值，任何捨入都填不平那段距離）；而且確定性門檻有時輸給隨機捨入，後者在平均上能做得更好。