動機
局部划算的購買未必帶來最便宜的完整方案。集合覆蓋把這個矛盾具體化:一個集合可能覆蓋許多尚未滿足的要求,卻留下難以處理、成本高昂的剩餘要求。近似分析不假裝困難消失,而是證明指定的可行輸出成本至多為最優值的受控倍數。
本篇在同一模型發展三種分析。貪心在首次覆蓋要求時收費;線性規劃容許分數購買,提供下界;原始—對偶算法同時構造覆蓋與下界證書。它們的近似因子來自不同結構參數,應比較保證而不只比較程序。
定義
定義 4.3.1
(加權集合覆蓋及其參數)
有限全集 有 個元素,可選集合為 ,其聯集為 。集合 的有限成本 非負。所選集合聯集為 時稱為覆蓋,成本為所選成本總和。以 表示最小覆蓋成本。令 , 為任何一元素所屬可選集合數的最大值。可行性保證 。
集合按標號視為不同選項,即使內容相同也可不同。成本非負,所以解無需重複選同一集合;空集合可忽略。容許零成本,保證寫成不等式,避免除以可能為零的最優值。計算上可用有理成本及明列的關聯數據;近似證明本身只需精確有限運算。
貪心維持未覆蓋集合 ,在 的選項中,選使 最小者,再從 移去新覆蓋元素。固定的平手規則均可。未完成時總有合資格集合,每步至少覆蓋一新元素,故最多選 次。若分母計入已覆蓋元素,便是另一算法。
定義 4.3.2
(分數覆蓋與對偶裝填)
分數覆蓋規劃最小化 ,條件為
對偶裝填規劃最大化 ,條件為
把分數的符號約束換成 ,便得精確的整數規劃表述。整數覆蓋提供這種可行的零一向量 。可行對偶為每元素指定非負價格,而不讓任何可選集合的總元素價格超過成本。
以下不需要強對偶定理,會直接證明下界性質。計算最優分數解是另一最優化任務;捨入定理假設已提供該解,並未實現線性規劃求解器。
概念視角代數
兩個參數就是行和與列和
設 為 - 關聯矩陣,當 時 。則 是最大的列和, 是最大的行和。原問題是 ,約束為 ;對偶問題是 ,約束為 。
定理 / 命題
定理 4.3.3
(調和貪心近似)
令 。貪心覆蓋成本至多為 ,因而至多為 。更強地,其成本至多為分數最優值的 倍。
定理 4.3.4
(頻率捨入及原始—對偶算法)
對任何可行分數覆蓋 ,選取全部 的集合可得覆蓋,成本至多 。另有直接構造覆蓋及可行對偶 的算法,使成本至多 ,無需先求解分數規劃。
證明思路或證明
證明
(弱對偶性)
先證弱對偶。任意可行分數覆蓋 及可行對偶 ,由非負性及兩類約束,有
中間等式只是重排有限的元素—集合關聯和。因此每個可行對偶值都是每個覆蓋成本的下界。即使不知道最優解,也可用簡單不等式檢查這張證書。
對貪心購買收費
證明
(以分攤與弱對偶證明貪心)
貪心以成本 覆蓋 個新元素時,每個新元素收費 。每元素只收一次,全部費用總和恰等於所選總成本。集合可重疊;此規則避免同一元素因重疊而在帳目重複付款。
固定任意大小 的非空可選集合 ,不要求它被選。按首次覆蓋時間排列其元素,同一步中的平手任意排列。在覆蓋其第 元素的那次選擇之前, 至少還有 個未覆蓋元素。當時 也是合資格方案,因此貪心比率及元素費用滿足
相加得 。所以 對全部集合約束均可行,包括空集合。弱對偶給出
其中 為分數最優值。最後一式是因為最小化問題中,整數可行解只是分數可行解的子集。也可與任意分數可行成本比較,避免假定最優解存在;本模型其實存在最優解,因為把每個座標截於一不會破壞可行性或增加成本,留下緊緻可行域。
由 得較弱的 版本。對 , 單調遞減,所以 ,相加便得 。這是最壞保證,不表示每個輸出達到該界。若最優值為零,同一組非負不等式也迫使貪心成本為零。
門檻捨入用頻率而非集合大小
證明
(門檻捨入覆蓋每個元素)
取可行分數覆蓋 ,固定元素 。它最多屬於 個集合。若這些座標全嚴格小於 ,總和便嚴格小於一,違反覆蓋約束。因此至少一個包含它的集合被門檻規則選中,對全部元素皆如此。
對每個選中 ,,所以 。先對選中者相加,再用成本非負加入未選項,便得成本界。門檻須包含等號;排除恰為 的座標,可能漏覆蓋元素。即使分數解成本高,仍可捨入,但只有最優或近乎最優分數解,才提供相應的整數最優比較。
與 描述不同結構。一集合可很大,但每元素只屬兩集合;也可每集合很小,卻有一元素出現在許多集合。調和保證受最大集合大小控制,門檻與下面的直接構造受最大元素頻率控制,不能在證明中任意互換。
一邊建覆蓋,一邊提高對偶價格
證明
(原始—對偶構造)
起初 ,未選任何集合。尚有未覆蓋元素 時,只提高 ,直到某包含它的集合緊約束,即元素價格總和等於其成本。選一個這種集合,標記其全部元素已覆蓋。若合資格集合已緊,便不加價而直接選取;零成本不造成除法或進展問題。
提高的數值可明確計算:對每個包含 的集合,求非負鬆弛量 ,提高其最小值。至少有一個這種集合,成本有限,不含 的約束不變,包含者的鬆弛量恰減去該值,故不會變負,且至少一個變緊。對偶可行性因而保持。
已選集合不包含任何當前未覆蓋元素,所以提高 不改變它們的總價,每個已選集合到終止時仍緊。每次至少覆蓋一新元素,最多 步。完成時
證明只需價格可行、所選約束緊及頻率界,從未聲稱所構造對偶最優。事後刪去多餘集合可減少成本,卻不是保證所必需。
證明透視
兩種證書的不等式方向相反
可行覆蓋給出最優值的上界,可行對偶給出下界;每個分析都把前者與後者的受控倍數聯繫起來,但各假設用在不同的地方。貪心要求每個集合 在先前每一步都是合格的備選,由此得到 ,再用 縮放以恢復對偶可行性。原始—對偶構造每一步保持可行:只把一個價格抬高到最小鬆弛量為止;並使已選集合保持緊,因為只有未覆蓋元素的價格才會改變。其最後計算的關鍵一步是交換對集合與元素的求和次序:緊性把成本化為 ,頻率界再把這個個數化為因子 。每個不等式都用到成本與價格的非負性;缺少它,與 的比較便不成立。
例題詳解
例題 4.3.5
(貪心可能付三,最優只需二)
取 ,單位成本集合 、、。貪心先選 ,比率 小於 ;其後五、六迫使再選 ,成本三。但 已能以二覆蓋全部,且五只在 、六只在 ,兩者必需。對偶 、其餘零可證下界二。局部划算未保持精確最優。
例題 4.3.6
(分數三角形與捨入落差)
,三個二元素子集各成本一。整數覆蓋需兩集合。各設 ,分數成本 ;各元素價格 對偶可行且同值。弱對偶證明分數值最優。此時 ,門檻捨入選全部三集合,成本三恰為分數值兩倍,而整數最優只有二。同一實例的不同合法算法可以品質不同。
例題 4.3.7
(三角形上的直接原始—對偶執行)
同一實例由零價格開始,選未覆蓋 並加到一。、 均變緊,選 。只餘 ,但 已緊,無需改價即可選。覆蓋成本二,可行對偶值一,符合二倍保證,而此整數輸出其實最優。算法證明不要求對偶也最優。
反例模式
不能隨意把門檻改成嚴格不等式
分數三角形的全部座標恰為 。若只選嚴格大於 者,就沒有任何集合,甚麼也沒覆蓋。修正是已證的 ,包含等號。浮點容差需要另有理由的可行性修補,數學門檻證明不會自動保證任意數值實現。
常見錯誤
常見錯誤
(把鬆弛的界方向弄反)
最小化鬆弛給下界,最大化鬆弛給上界,反向會破壞近似比證明。可行對偶也須滿足每個集合約束,而不只是被選者。未縮放的貪心費用一般違反部分約束,這正是調和縮放的用途。
常見錯誤
(抬高已覆蓋元素的價格)
原始—對偶證明依賴不提高已覆蓋元素的價格;否則可破壞既選集合的緊性或約束。重疊無害,是因為最後明確用 限制重數,並未假定所選集合互不相交。
總結
收費把貪心比率在調和縮放後轉成對偶可行下界。頻率捨入把分數覆蓋變成整數覆蓋。直接原始—對偶方法在構造期間保持可行性及緊性。這些論證展示局部選擇、鬆弛與下界如何建立嚴格近似保證,而非宣稱精確最優化。
練習
快速檢查
(若每個可選集合最多三元素,明確寫出調和保證,並與按整個全集大小的界比較。)
計算 ,並注意 。
解答 · 答案
,所以貪心成本至多最優的 倍;若 ,可用更小的 。由 ,不會比 差。全集可以很大,集合仍很小。
快速檢查
(在分數三角形,為何全設 雖非負,卻不是合法對偶?)
檢查某個二元素集合的約束。
解答 · 答案
每個二元素集合價格總和為二,超過成本一。非負只滿足符號條件,所有集合上界仍須成立。縮至每個一半便得例題的最優可行對偶。
快速檢查
(把有限無自環圖的加權頂點覆蓋建模為集合覆蓋,推出二倍門檻捨入;處理孤立頂點及無邊情形。)
先選定全集、集合及其成本,再求頻率 。
解答 · 答案
以邊為全集,每頂點對應其全部關聯邊的集合,成本為非負頂點權。每邊恰屬兩集合,所以 。分數頂點覆蓋在每邊的兩端值之和至少一,選全部值至少一半的頂點便覆蓋每邊,且成本至多分數目標兩倍。孤立頂點對應空集合,可不選;若無邊,空選已是零成本最優,另行處理,不套用本篇 約定。
快速檢查
(可行實例中成本全部為零,解釋兩算法的終止及目標界。)
考察所有成本為零時的貪心比率與緊約束。
解答 · 答案
貪心總能選合資格的零比率集合,每步覆蓋一新元素,最多 步、成本零。原始—對偶的零價格使全部約束已緊,每步無加價便選包含未覆蓋元素的緊集合,同樣有進展並以零成本終止。不等式仍有效,直接除以 OPT 卻不合法。