設置封面的近似值

Question

我開始學習近似算法， 我正在讀一本關於這方面的書，我不明白集合封面算法的分析。

有人可以解釋引理2.3嗎？ 因爲它很短，但我不明白它...

http://view.samurajdata.se/psview.php?id=0482e9ff&page=13

Answer 1

的算法分配「價格」 price(e)以該價格是用來設定S成本宇宙U的每個元素覆蓋e除以集合S新覆蓋的元素的數量（由於算法的定義，任何已經覆蓋的元素必須已經被先前集合分配了更低的價格）。

存在一個最佳的解決方案，它選擇一組總成本爲OPT的套裝。由於該解決方案涵蓋所有元素，因此它涵蓋了尚未涵蓋的任何元素。以成本OPT覆蓋剩餘的元素（集合CBar在證明的表示中）將意味着通過成本效益（又名價格）的定義覆蓋每個元素在成本效益OPT/|CBar|。由於最佳解決方案包含一個覆蓋所有剩餘元素的集合，假設我們從包含至少一個剩餘元素（標記2.3中的e_k）的最優解中選取一組集合S。請注意，我們正在選擇成本效益最好的組合，因此其成本效益至少應與最佳解決方案OPT/|CBar|中的組的平均成本效益一樣好。

最後一部分是由於定義，|CBar|=n-(k-1)=n-k+1爲k-1元素已被覆蓋，我們正在尋找覆蓋元素k。因此，S的成本效益以及因此price(e_k)以OPT/(n-k+1)爲界。