Set Cover 的贪心近似

每轮选择只为尚未覆盖的元素创造价值，因此分母必须随覆盖状态缩小。把集合成本平均收给本轮新覆盖元素后，任意最优集合中第 $j$ 个较晚被覆盖的元素，面对的剩余候选只会更少；这些收费形成调和级数，而不是每轮都付同一个最坏比率。

图中的 $C:4,A:3,B:1$ 标记各轮新增覆盖数。例如八元素宇宙上取成本均为 $1$ 的 $C=\{4,5,6,7\}$、$A=\{1,2,3\}$、$B=\{8\}$，即得到所画的剩余集合序列；后面的六元素例子另用于比较不同成本。

真实选择图像 ​

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

边界与相邻问题 ​

$H_m\le 1+\ln m$，且 $H_m=\ln m+\gamma +o(1)$，其中 $\gamma$ 是 Euler 常数；因此保证随宇宙大小按对数增长。最大覆盖问题给定只能选 $k$ 个集合、目标最大化覆盖量，具有不同的 $1-1/e$ 分析。参数 $|U|$ 是宇宙元素数；若改用最大集合大小可得更细 $H_d$，必须明确 $d$。

算法每步选择单位成本覆盖新元素最多的集合，是贪心算法理路贪心算法Greedy algorithm每一步作局部最优且不回溯选择的算法设计范式。；调和数近似保证来自把每个新覆盖元素按当步单位代价收费，并与最优解中某个集合尚未覆盖的元素数比较。

实现与 tie-breaking ​

每轮需要按当前未覆盖集重新评估候选，求交集的访问成本也须计入。无权版可维护按当前 uncovered count 的桶或懒优先队列；选出候选后重新计算其真实新增量，过期键就更新再弹。若成本以有理数给出，可交叉相乘精确比较加权比率，并计入整数位长；对任意实数成本，则须明确采用精确算术与比较 oracle。

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

加权实例的选择轨迹 ​

取 $U=\{1,2,3,4,5,6\}$，$A=\{1,2,6\}$ 成本 $3$，$B=\{6\}$ 成本 $2$，$C=\{1,2,3,4,5\}$ 成本 $4$。初始单位新增成本分别为 $1,2,4/5$，所以先选 $C$；此时只剩元素 $6$，$A$ 的比例变为 $3$，$B$ 仍为 $2$，第二轮选 $B$，总成本为 $6$。若沿用最初排序则会错误地把 $A$ 排在 $B$ 前面。

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

若使用元素关联表，总关联数为 $M=\sum _{S\in \mathcal{S}}|S|$，逐轮重新扫描全部关联和集合可在 $O(m(M+|\mathcal{S}|))$ 次基本访问内完成；空集与不可行分支的预处理另需 $O(M+|\mathcal{S}|+m)$。懒堆是可选实现，不改变这份保守的显式输入成本上界。

独立舍入加最便宜集合补选理路随机舍入randomized rounding从连续松弛解生成随机离散解，以覆盖补选证明每次可行性与期望成本，并区分独立坐标与共享超平面的舍入。提供另一条覆盖路线：先解LP，再抽样并修复所有遗漏，每次输出都可行，而成本相对于LP的保证在期望意义下成立。本页贪心的调和数界则对每条实际选择轨迹成立，两者不能混称为相同的逐次保证。