集合覆蓋的貪婪 ln n 近似（greedy ln n approximation for set cover）

你有一個包含 n 個項目要覆蓋的全集（比方說 n 座要提供服務的城市），以及一堆可用的集合（服務區，每個覆蓋某些城市子集）。你想選出盡量少的集合，使每個項目至少落在一個被選集合裡。這就是集合覆蓋，而找出最少集合數是 NP 困難的。自然的貪婪規則令人難以抗拒：不斷抓那個覆蓋最多「尚未覆蓋」項目的集合。

具體地說：一開始全部未覆蓋。重複——在所有集合中，挑出覆蓋目前未覆蓋項目最多的那個，加入你的解，把它的項目標為已覆蓋——直到沒有東西未覆蓋。聰明之處在分析。設最佳解用 OPT 個集合。在任何時刻，那 OPT 個集合合起來覆蓋了所有剩餘的未覆蓋項目，所以由鴿籠原理，其中至少有一個覆蓋了剩餘量的至少 1/OPT 分；而貪婪選的那個至少覆蓋這麼多。於是每一步至少移除剩餘未覆蓋項目的 1/OPT 分，意思是剩餘數量每步乘上 (1 - 1/OPT) 縮小一次。從 n 出發，約 OPT * ln n 步後未覆蓋數降到 1 以下，亦即降到零。所以貪婪最多用約 OPT * ln n 個集合——一個 ln n 倍最佳的保證（更精確是 H_n = 1 + 1/2 + ... + 1/n，第 n 個調和數，約等於 ln n）。

為何重要、又卡在哪。集合覆蓋無所不在——設施選址、特徵選取、感測器覆蓋——而貪婪既簡單又是實務上的預設。驚人的事實是：這個 ln n 基本上是任何多項式演算法能做到的最佳：把集合覆蓋近似得比 (1 - o(1)) ln n 更好是 NP 困難的。所以不像頂點覆蓋（常數因子 2），集合覆蓋真的無法被近似到常數倍；那個對數的損失是無可避免的。誠實的提醒：ln n 是最壞情況的上限，在典型實例上貪婪好得多——但你不能指望那一點，而逼出完整 ln n 損失的實例確實存在。