集合覆盖贪心近似定理

概述

集合覆盖贪心近似定理（Greedy Set Cover Approximation Theorem）：对于集合覆盖问题，贪心算法可以找到一个不超过最优解 $H(d)$ 倍的近似解，其中 $H(d)={\sum }_{i=1}^d\frac{1}{i}\le \ln d+1$ 是第 $d$ 个调和数，$d$ 是最大集合的大小。

定理陈述

形式化陈述

集合覆盖问题：给定全集 $X=\{x_1,x_2,\dots ,x_n\}$ 和子集族 $\mathcal{S}=\{S_1,S_2,\dots ,S_m\}$，其中 $S_i\subseteq X$，${\bigcup }_{i=1}^m{S}_i=X$。目标是找到 $\mathcal{S}$ 的最小子族 $\mathcal{C}\subseteq \mathcal{S}$ 使得 ${\bigcup }_{S\in \mathcal{C}}S=X$。

贪心算法：每一步选择能覆盖最多未被覆盖元素的集合。

定理：设 $d={\max }_{S\in \mathcal{S}}|S|$，贪心算法输出的集合覆盖 $\mathcal{G}$ 满足： $|\mathcal{G}|\le H(d)\cdot |{\mathcal{C}}^{\ast }|$ 其中 ${\mathcal{C}}^{\ast }$ 是最优集合覆盖，$H(d)={\sum }_{i=1}^d\frac{1}{i}\le \ln d+1$。

特别地，当 $d=n$ 时，近似比为 $H(n)\le \ln n+1$。

贪心算法描述

GREEDY-SET-COVER(X, S):
    U = X                          // 未覆盖元素集合
    C = empty set                  // 选择的集合
    while U ≠ empty:
        选择 S ∈ S 使得 |S ∩ U| 最大
        C = C ∪ {S}
        U = U \ S
    return C

证明概要

证明思路（Charging Argument / 费用分摊论证）

证明的核心思想是费用分摊（charging argument）：将贪心算法的总费用合理地”分摊”到最优解中的每个集合上，证明每个最优集合最多承担 $H(d)$ 的费用。

关键引理：调和数不等式

对任意正整数 $k$ 和 $d$，有： $H(d)-H(k-1)={\sum }_{i=k}^d\frac{1}{i}\le {\int }_{k-1}^d\frac{1}{x}dx=\ln d-\ln (k-1)=\ln \frac{d}{k-1}$

证明主体

步骤1：定义费用函数

设贪心算法依次选择的集合为 $S_1,S_2,\dots ,S_k$。定义第 $i$ 步选择 $S_i$ 时的单位费用为： ${\text{cost}}_i=\frac{1}{|S_i\cap U_i|}$ 其中 $U_i$ 是第 $i$ 步之前尚未被覆盖的元素集合。

贪心算法的总费用为： $\text{total}={\sum }_{i=1}^k|S_i\cap U_i|\cdot {\text{cost}}_i={\sum }_{i=1}^{k}1=k=|\mathcal{G}|$

步骤2：对最优解中的集合分摊费用

考虑最优解中的任意集合 $S^{\ast }\in {\mathcal{C}}^{\ast }$，设 $|S^{\ast }|=d^{\ast }\le d$。将 $S^{\ast }$ 中的元素按被贪心算法覆盖的先后顺序排列为 $x_1,x_2,\dots ,x_{d^{\ast }}$。

步骤3：界定每个元素的费用

当元素 $x_j$ 在第 $i_j$ 步被覆盖时，$S^{\ast }$ 中仍有至少 $d^{\ast }-j+1$ 个元素未被覆盖（因为 $x_j,x_{j+1},\dots ,x_{d^{\ast }}$ 都未覆盖）。

贪心算法选择了覆盖最多未覆盖元素的集合，所以： $|S_{i_j}\cap U_{i_j}|\ge |S^{\ast }\cap U_{i_j}|\ge d^{\ast }-j+1$

因此 $x_j$ 被分摊的费用为： ${\text{cost}}_{i_j}=\frac{1}{|S_{i_j}\cap U_{i_j}|}\le \frac{1}{d^{\ast }-j+1}$

步骤4：汇总每个最优集合的费用

${\sum }_{x\in S^{\ast }}\text{cost}(x)\le {\sum }_{j=1}^{d^{\ast }}\frac{1}{d^{\ast }-j+1}={\sum }_{i=1}^{d^{\ast }}\frac{1}{i}=H(d^{\ast })\le H(d)$

步骤5：总费用上界

$|\mathcal{G}|={\sum }_{x\in X}\text{cost}(x)={\sum }_{S^{\ast }\in {\mathcal{C}}^{\ast }}{\sum }_{x\in S^{\ast }}\text{cost}(x)\le {\sum }_{S^{\ast }\in {\mathcal{C}}^{\ast }}H(d)=H(d)\cdot |{\mathcal{C}}^{\ast }|$

参考资源：

• UCR贪心集合覆盖算法历史综述：http://www.cs.ucr.edu/~neal/Papers/Young08SetCover.pdf
• CMU 15-854近似算法讲义：https://www.cs.cmu.edu/~15850/notes/lec24.pdf
• MIT 6.854近似算法讲义：https://people.csail.mit.edu/ghaffari/AA18/Notes/S3.pdf
• UMD CMSC451集合覆盖讲义：http://www.cs.umd.edu/class/spring2025/cmsc451-0101/Lects/lect07-set-cover.pdf

关键推论

• NP-hard性：集合覆盖问题是NP-hard的，因此除非P=NP，否则不存在多项式时间的精确算法
• 不可改进性（除非P=NP）：除非P=NP，集合覆盖问题不存在 $c\cdot \ln n$ 近似算法（$c<1$），即 $\ln n$ 的量级是最优的
• 加权推广：加权集合覆盖问题中，贪心算法同样给出 $H(d)$-近似，其中 $d$ 是最大集合大小
• 与顶点覆盖的关系：顶点覆盖是集合覆盖的特例（$d=2$），$H(2)=1+1/2=3/2$，但顶点覆盖有更好的 $2$-近似算法

应用场景

在算法导论（CLRS）Ch35近似算法中的具体应用：

1. 设施选址：在候选位置中选择最少的设施覆盖所有需求点
2. 网络监控：选择最少的传感器节点覆盖整个监控区域
3. 信息检索：用最少的查询词组合覆盖所有相关文档
4. 贪心算法：集合覆盖贪心算法是贪心策略在NP-hard问题上的经典成功案例，展示了贪心方法即使无法获得最优解，仍能提供有理论保证的近似解

参见

• 贪心算法
• 集合
• 集合运算
• 鸽巢原理
• 容斥原理