隨機捨入（randomized rounding）

確定性的 LP 捨入用固定門檻——分數至少 1/2 就捨上去。隨機捨入採取更富想像力的觀點：把每個分數值當作「機率」，擲一枚有偏的硬幣。若 LP 說 x_i = 0.7，就以機率 0.7 把變數設為 1、以機率 0.3 設為 0。運氣的巧合便會在平均上合謀，給出一個接近 LP 最佳值的解——而分析用的是期望值與尾界，而非逐情形的論證。

為何隨機有幫助？兩個理由匯聚。第一，期望值的線性性質讓期望成本算起來輕而易舉：變數 i 的期望貢獻恰好是 x_i（它以機率 x_i 變成 1），所以期望總成本恰好是 x_i 之和 = LP-OPT。一筆帶過，平均而言你付的正是 LP 值。第二，為了滿足約束，你對機率進行推理：在覆蓋問題中，某條邊或某個子句可能以某個小機率被留下未覆蓋，而你界定那個失敗機會。標準做法是獨立捨入，然後要嘛重抽直到所有約束成立，要嘛把機率略微放大（以機率 min(1, c * x_i) 把 x_i 捨成 1，c 是個小因子，例如 c = ln n），使任何單一約束失敗的機會變得極小。接著一個切爾諾夫界或聯集界證明：高機率下「所有」約束同時被滿足，而成本仍維持在 LP-OPT 的小因子內。對集合覆蓋，這套配方正好重現 O(log n) 的保證。

隨機捨入是個主力，正因為它通用且數學乾淨：期望值處理成本、集中不等式處理可行性，同一套模板涵蓋集合覆蓋、MAX-SAT、最小化壅塞的路由等等。誠實的細節：演算法是隨機的，所以它的保證是「期望上」或「高機率」，不是每次執行都確定無誤——不過你常能重抽或去隨機化來把它變硬。而且它並不神奇：整數性差距仍然界定捨入後的解能多好，因為你捨入的還是同一個鬆弛。