Set Cover 的贪心近似

算法 ​

给集合公理库集合Set由确定成员组成的数学对象；成员关系而非表示顺序决定集合。宇宙 $U$、集合族 $\mathcal{S}$ 和非负成本 $c(S)$。维护未覆盖集 $R$；每步选择新增覆盖非空且

$$\frac{c(S)}{|S\cap R|}$$

最小的集合，加入解并从 $R$ 删除其覆盖元素。无权情形等价于选覆盖未覆盖元素最多的集合；覆盖数为零的集合不可作为候选。

收费证明 ​

选择 $S$ 时把成本均摊给刚覆盖元素，每个收 $c(S)/|S\cap R|$，算法总成本等于全部收费和。固定最优解中的集合 $T$，按其元素被贪心覆盖的先后看：当还剩 $r$ 个 $T$ 元素未覆盖时，$T$ 自身单位成本至多 $c(T)/r$，贪心收费不超过该值。因此 $T$ 内总收费至多

$$c(T)(1+\frac{1}{2}+\cdots +\frac{1}{|T|})\le c(T)H_{|U|}.$$

把每个元素归给一个覆盖它的最优集合求和，得 ALG$\le H_{|U|}$OPT。

真实选择图像 ​

布置监测站覆盖一组区域时，一个站虽覆盖面大但成本也高；加权规则比较“每新增覆盖一个尚未监测区域的成本”，已覆盖区域不再贡献分母。无权规则若直接用于成本差异大的站点，会偏离证明。

边界与相邻问题 ​

$H_{|U|}\approx \ln |U|+1$ 不是常数，且在标准复杂度假设下对数量级基本紧。最大覆盖问题给定只能选 $k$ 个集合、目标最大化覆盖量，具有不同的 $1-1/e$ 分析。参数 $|U|$ 是宇宙元素数；若改用最大集合大小可得更细 $H_d$，必须明确 $d$。

实现与 tie-breaking ​

直接每轮重算所有集合新增覆盖成本可能为 $O(|U||\mathcal{S}|)$ 甚至更高。无权版可维护按当前 uncovered count 的桶或懒优先队列；选出候选后重新计算其真实新增量，过期键就更新再弹。加权比率是有理数，比较可交叉相乘避免浮点误判。

平局任取都保留近似证明，因为只用“单位成本不大于任何候选”。但输出若要求可重复，仍应以集合 ID 固定 tie-break。预处理还要确认每个元素至少属于一个集合，否则实例不可覆盖。

加权实例的选择轨迹 ​

设未覆盖元素为 6 个，集合 $A$ 成本 3 可新增覆盖 3 个，$B$ 成本 2 可新增覆盖 1 个，$C$ 成本 4 可新增覆盖 5 个。当前单位新增成本分别为 1、2、0.8，所以先选 $C$；重算后 $A$ 也许只剩一个新元素，比例会从 1 变为 3，不能沿用初始排序。

实现可用懒堆保存上次计算的比例：弹出候选后按当前未覆盖集重算，只有仍不劣于堆顶才真正选择，否则以新键放回。这个技巧减少实际重算，却不改变最坏近似证明；tie-breaking 影响具体解，不影响 $H_{|U|}$ 上界。

若某元素不属于任何集合，实例本身不可行，算法应在 $R$ 非空而所有新增覆盖为零时报告失败。最大覆盖问题有选择个数预算、目标是尽量多覆盖，与“必须覆盖全部元素”的 Set Cover 方向不同。

参考资料

• Václav Chvátal, A Greedy Heuristic for the Set-Covering Problem, Mathematics of Operations Research, 1979.
• David Johnson, Approximation Algorithms for Combinatorial Problems, JCSS, 1974.