動機
分數解可以把一個單位的覆蓋量分攤給許多集合,而真正的覆蓋必須整個地選取集合。獨立的隨機選擇讓分數值來指引這個決定。其中的核心矛盾在於:成本低廉的隨機選擇可能漏掉某個元素,因此我們必須同時控制期望成本與可行性。重複進行選擇,並對未被覆蓋的元素明確地加以修補,便得到一個完整的算法,而不只是一個高概率的建議。
定義
定義 4.1.1
(集合覆蓋及其分數鬆弛)
設 是含有 個元素的有限全集,並設 ,其成本為 。假設每個元素至少屬於一個集合。覆蓋是指聯集等於 的一族集合。分數鬆弛問題是:在對每個 滿足 且 的約束下,最小化 。設 為任一可行的分數解,並令 ;最優分數解的成本不會高於最優整數覆蓋的成本,因為每個整數覆蓋都給出一個可行的零一解。
定義 4.1.2
(帶修補的隨機捨入)
固定整數 。對每個集合 獨立地以概率 選取它。等價地,進行 次獨立試驗,每次的選取概率為 ,只要至少一次成功便保留該集合。之後,對每個未被覆蓋的元素,加入一個包含它的成本最低的集合。重複的集合只計一次費用。由可覆蓋性假設,這個修補步驟是良定義的。
定理
定理 4.1.3
(帶修補的捨入的覆蓋性與成本)
該算法總是返回一個覆蓋,其期望成本至多為 。特別地,當 時取 ,期望成本至多為 ;因此當 為最優分數解時,期望成本至多是最優整數覆蓋成本的該倍數。當 時,取 得到界 。
定理 4.1.4
(修補之前的高概率覆蓋)
對任意可行的分數解,隨機選擇之後至少有一個元素未被覆蓋的概率至多為 。特別地,對 ,取 可使該概率至多為 。
證明思路
證明
(聯集界、線性性與修補的記賬)
對固定的元素 ,由各集合的選擇相互獨立,得
這裏用到當 時 ;該公式對 的情形同樣成立。把這些概率對所有元素求和,就證明了聯集界。不同元素對應的事件之間無須相互獨立。
集合 被選中的概率至多為 ,這是對它的 次試驗使用聯集界的結果。因此由期望的線性性,無論各集合之間如何重疊,初始成本都以 為界。設 為包含 的最便宜集合的成本。由於所有這類集合的成本都至少為 ,分數可行性給出
實際的修補成本至多為 ,其中 是「 最初未被覆蓋」的指示變量;即使一個新加入的集合同時修補了多個元素,這仍然是一個上界。取期望後得到至多 。把兩個界相加即證明了定理。修補使可行性成為必然;期望成本的保證並不是對每一種結果都成立的確定性上界。
證明透視
線性性的兩種用法
期望成本是對集合求和,而期望修補成本是對元素求和。兩個計算都不要求這些成本項相互獨立。獨立性在更早的步驟中使用,即用來分解「包含某個固定元素的所有集合都未被選中」的概率。
例題詳解
例題 4.1.5
(集合構成的三角形)
設 ,三個單位成本的集合為 、 和 。令每個 是可行的,此時 。取 ,每個集合被選中的概率為 。每個元素被漏掉的概率為 。期望初始成本為 ;一般的修補界為 ,因為每個最便宜的覆蓋集合成本為一。因此期望總成本至多為 。真正的最優整數成本為 。
例題 4.1.6
(被迫的選擇)
若元素 恰好只屬於一個集合 ,則可行性與 迫使 。對任意正的 ,捨入都以概率一選取 。若認為每個元素的失敗概率恰好等於 ,那就錯了:那只是一個統一的上界,不是等式。
例題 4.1.7
(選取失敗概率目標)
對 和 ,取 即足夠。修補之前出現任何未覆蓋元素的概率至多為 。隨後修補使每次運行都得到一個覆蓋。該定理控制的是期望成本;它並不斷言每次運行的成本都至多為 。
常見錯誤
反例模式
每個分數只捨入一次可能失敗
在三角形的例子中只做一次試驗時,包含元素 的兩個集合都未被選中的概率為 。因此對可行線性規劃解進行獨立捨入並不會自動產生一個覆蓋。重複試驗降低失敗概率,而修補則消除剩餘的不可行風險。
常見錯誤
(期望成本不是每次運行的保證)
期望成本與失敗概率是兩個獨立的陳述。僅有較小的期望成本,並不能保證某一次具體運行的成本低;而較小的失敗概率,也不會使未覆蓋的結果變成可行。此外,線性規劃下界要求問題是最小化問題且成本如所設為非負;近似保證的方向必須對照該下界來核對。
為甚麼會出現對數
對單個元素而言,界 隨獨立試驗次數指數下降。為使全部 個元素同時有很大把握被覆蓋,聯集界把它乘以 。取 與 同階,恰好抵銷這個因子。這就是證明中對數的來源;它並不是說每個具體實例都需要這麼多次試驗。在被迫選擇的例子中,一次試驗就能確定地覆蓋該特殊元素。聯集界把所有元素都當作具有最壞容許的失敗概率,因而可能相當鬆。
線性規劃還提供了一個在運行捨入之前就有用的數值證書。對任何整數覆蓋,把被選集合的 取為 、其餘取為 ,就得到成本相同的可行分數點。因此,分數最優值的任何下界都是每個整數覆蓋成本的下界。然而,任意一個可行的分數點只是分數最優值的上界,並不自動成為整數最優值的下界。因此,與整數最優值的近似比較要用到最優分數解(或另行證明過的對它的近似);相對於 的成本界則對每個可行分數點都成立。
例題 4.1.8
(分數可行並不意味著最優)
設 ,取兩個都等於 的集合,成本分別為 和 。選擇 是分數可行的,且 ,而整數最優成本與分數最優成本都是 。捨入定理仍然以 來界定期望成本,但若代入 就是錯誤的。選取最優線性規劃解才能使該比較成立。
獨立性、修補與實現
一種實現方式是為每個集合抽取一個概率為 的獨立伯努利(Bernoulli)變量。等價的重複試驗描述是一種證明工具,也是實現同一分佈的方式:屬於不同集合的各次試驗必須全部相互獨立。兩個元素未被覆蓋的事件一般並不獨立,因為同一個隨機選出的集合可能同時包含這兩個元素。聯集界有意避免了需要它們的聯合分佈。例如,若一個集合同時包含兩個元素,則未選中它會使兩個元素同時未被覆蓋。
修補可以這樣實現:在隨機選擇之後掃描全集,然後為每個仍未被覆蓋的元素加入一個最便宜的、包含它的可用集合。證明為每個最初未被覆蓋的元素至多計入 。如果先前的修補恰好也覆蓋了之後的某個元素,那麼對後者的計費可能是不必要的,但無論如何計入仍保持為上界。因此分析不依賴於修補的次序。成本非負保證了把一個加入的集合重複計算不會低估真實成本;重複的集合只需儲存一次。
理想化的證明假定概率精確且線性規劃解最優。在實際實現中,必須說明所用的算術、求解器容差與隨機位元模型。一個可行且近似最優的分數向量仍可用同樣的證明進行捨入,其目標值為其實際值 ;若要得到相對於整數最優值的指定近似因子,還需要對該值有已證明的界。對一個近似可行的向量,若不先修正違反的約束就進行捨入,則 的估計不能成立:每個元素所關聯的各分數之和必須如假設那樣至少為一。
修補估計可以改進為 ,而不是 。這一更精細的形式直接來自期望的線性性,在具體實例上可能小得多。較粗的界則使近似因子僅依賴於 與線性規劃值。例如,若所有元素都有便宜的集合可用,但分數解還為其他昂貴的集合付費,那麼 可以遠低於 。
一個有用的概率計算
當需要明確的失敗閾值時,應以正確的方向使用概率界。例如,若 而期望的上界為 ,則只需 。取整數上取整得 ,且 。這是一個充分的選擇,而不是證明在某個具體實例上十三次試驗不可能。實際概率可能小得多,因為分數約束可能有鬆弛,或者因為失敗事件之間高度重疊。
另外的馬爾可夫(Markov)界可以把期望陳述轉化為成本的尾部陳述。由於總成本 非負,對任意 有 。因此,以至少 的概率,修補後的覆蓋成本至多為 (邊界情形可無害地照此理解)。這個結論在常數上比期望成本的保證更弱,但它給出了單次運行的概率。如果 ,成本非負且期望界為零,所以成本幾乎必然為零;此時無須在零閾值處應用馬爾可夫不等式。獨立重複可以降低所有運行都超過閾值的機會;選取修補後成本最低的覆蓋仍保持可行性。重複之間的獨立性必須加以安排,且在實現中必須計入生成這些重複的成本。
對隨機結果的確定性檢查
隨機選擇一旦完成,檢查輸出是否為覆蓋就不再需要任何概率計算。掃描被選中的集合,標記它們包含的每個元素,並驗證所有元素都被標記。只要輸入滿足可覆蓋性假設,且最便宜的包含集合被正確找到,修補步驟就保證這一檢查會通過。如果輸入中有元素不屬於任何可用集合,則原實例沒有可行覆蓋,其分數約束也不可行;修補定理有意排除這種情形。
常見錯誤
(同一個近似陳述中的兩種不同比較)
近似陳述包含兩個不同的比較。第一,輸出成本的數學期望以提供給捨入的分數點的目標值的一個倍數為界。第二,最優分數值以最小整數覆蓋成本為上界。第二個比較用到可行集合之間的包含關係:所有整數覆蓋都產生分數可行點,而鬆弛問題可能還有額外的分數點。弄混哪一個可行集合更大,就會使結論反向。分數最優值可以嚴格更小,如在三角形例子中它至多為一又二分之一,而最便宜的整數覆蓋成本為二。
隨機選擇規則也有直觀的極限情形。當某個分數變量為零時,其集合在捨入過程中永遠不會被選中,但若它對某個未被覆蓋的元素而言是最便宜的,修補仍可能把它加入。當某個變量為一時,其集合以概率一被選中。對中間值,概率隨試驗次數增加而增大,但永遠不超過一。若直接把 當作概率,則只要該數超過一就會失效。它作為實際概率的上界仍然有效,而期望成本的證明正是這樣使用它的。
該定理假設成本非負。如果容許負成本的集合,多選一個集合可能降低總成本,而對某個集合重複計費可能使修補論證中的不等式反向。人們可以透過先選取負成本集合並修改實例來預處理這樣的不同模型,但那需要另行分析。在這裏,成本非負的假設使每個部分和都可以由整個分數目標值界定,並使修補成本的比較一目了然。
總結
隨機捨入把分數隸屬度轉化為獨立的集合選擇。指數衰減界定漏掉某一元素的概率;聯集界控制全部元素;最便宜集合的修補則帶來確定的可行性以及對數級的期望近似界。
練習
快速檢查
(在三角形例子中,當 時,求沒有任何集合被選中的概率。)
每個集合不被選中的概率相同。
解答 · 答案
每個集合各自以概率 不被選中,且相互獨立,所以概率為 。
快速檢查
(若 且 ,給出任何元素未被覆蓋的概率的聯集界上界。)
使用高概率覆蓋定理中的界。
解答 · 答案
至多為 。該界不必是緊的。
快速檢查
(即使「各元素被覆蓋」的事件相互依賴,為甚麼仍可以把被選中集合的期望成本相加?)
期望的哪一條性質不需要獨立性?
解答 · 答案
期望的線性性無須獨立性即成立。集合選擇的獨立性用於界定漏掉某個固定元素的概率,而不是用於把期望成本相加。
快速檢查
(設 ,且 是分數鬆弛問題的最優解。當 時,給出該定理的期望近似因子。)
把 、 代入 。
解答 · 答案
該界為 。由於分數最優值至多等於整數最優值,同一個數也就是期望近似因子。