29篇区分了求解、验证和困难性。遇到难以精确求解的优化问题，一种选择是保留可行性，允许目标值偏离最优，但为偏离程度给出对所有合法输入成立的保证。

对于目标非负的最小化问题，记算法返回值为ALG、最优值为OPT。ρ近似要求ALG≤ρOPT，同时算法在输入编码长度的多项式时间内结束。直接写不等式可以覆盖OPT=0；写ALG/OPT时还得处理分母为零。下面两个保证是确定性的最坏情况保证，不是随机输入上的平均表现，也不是运行时间的摊还界。

点覆盖中的一组不相交边

输入是n个顶点、m条边的无向简单图。点覆盖是一组顶点C，使每条边至少有一个端点属于C；无权版本要求最小化|C|。这与27篇的匹配不同：匹配选择边，要求边不共享端点；覆盖选择顶点，要求所有边得到覆盖。

顺序扫描边。如果当前边的两个端点都没有被选过，把这条边加入M，并把两个端点加入C。扫描结束，输出C。

M是一组匹配，因为加入新边时两端都未使用。它还是极大匹配：若有一条边与M完全不相交，这条边在被扫描时两端也必定未使用，就应该被加入，矛盾。极大只表示不能继续加边，不表示边数最大；不需要运行27篇的最大匹配算法，也不要求图是二分图。

C包含M的全部端点。若有一条边未被C覆盖，其两端就与M不相交，违反极大性。因此返回值可行。

任何点覆盖都必须触及M中的每条边。M的边互不共享端点，所以这些覆盖责任需要至少|M|个不同顶点。于是OPT≥|M|，而算法恰好选出2|M|个顶点，得到|C|≤2OPT。下界来自同一个输入上的匹配证书，不需要先求出OPT。

布尔数组标记顶点、每条边检查一次，核心算法需要O(n+m)时间、O(n)额外空间；保存输入边和返回的匹配另计O(m)与O(n)。这是单位成本顶点索引模型的最坏界。教学代码用Python集合保存选中顶点，因此代码中的成员查询与插入按期望常数成本分析；不能把这个实现的哈希成本写成最坏常数。实现还允许平行边，它们不改变证明；自环被拒绝。

极大性和无权条件不能省略

只有一条边的图，算法选择两个顶点，而最优只需一个，近似因子2已经达到。这个例子说明保证是可以取到的上界，不意味着输出通常恰好等于最优。

如果只取任意匹配而不要求极大，覆盖性会失败。两条互不相交的边，只选择其中一条的端点，另一条仍未覆盖。

直接把算法用于加权点覆盖则没有常数保证。单条边两端权重分别为1和K，选择两端的成本是K+1，最优成本为1。下一篇通过松弛与对偶处理权重，本篇的2近似结论仅用于无权版本。

集合覆盖每一步买到多少新元素

输入是有限全集U、集合S_1到S_q及非负成本c_i，每个S_i都是U的子集。输出一组集合索引，使它们的并集等于U，并最小化总成本。记N=|U|，d为输入集合的最大大小，L=Σ|S_i|为成员记录总数。

设X是尚未覆盖的元素集合。每一步只考虑|S_i∩X|>0的集合，选择c_i/|S_i∩X|最小者，把它加入答案，再从X中删除新覆盖的元素。比率相同按输入索引打破平局即可，证明不要求特定平局选择。

不能只按集合大小选。若U含两个元素，整个U成本为K，两个单点集合各成本1，忽略成本会买下K，而最优只花2。算法比较的是每个新增元素的成本，不是总大小，也不是包含已覆盖元素后的平均成本。

零成本集合只要还能覆盖新元素，就有比率0，正常参与选择。U为空时返回空方案，不计算log0或调和数H_0作为除数。若X非空却没有任何能新增覆盖的集合，则输入不可覆盖，不能把部分覆盖伪装成近似解。

把每次付款分给新覆盖的元素

某一步选中集合S，新增覆盖r个元素。给这r个元素各记费用α_e=c(S)/r。每个元素只在首次覆盖时收费，所有费用之和恰好等于算法总成本ALG。

固定任意输入集合T，大小为s，把它的元素按首次被覆盖的先后排列；同一步覆盖的元素任意排序。考虑其中第j个元素被覆盖时，T至少还有s−j+1个元素未覆盖。此时T本身也是一个候选，因此贪心选中的比率不超过c(T)/(s−j+1)。给该元素的费用正好就是选中比率，于是

∑e∈Tαe≤c(T)∑r=1s1r=c(T)Hs≤c(T)Hd.\sum_{e\in T}\alpha_e\le c(T)\sum_{r=1}^{s}\frac1r=c(T)H_s\le c(T)H_d.

同一步同时覆盖多个元素并不破坏这个比较：它们共享该步费用；排序越靠后的元素，右侧分母越小，允许的上界只会更大。

取一个最优覆盖，把上式对它选中的各集合求和。每个元素至少在一个最优集合中出现，且费用非负，重叠会使各集合的元素费用求和重复计费。因此ALG≤H_d OPT，其中H_d=1+1/2+…+1/d≤1+ln d。这个保证依赖最大集合大小，而不必一律使用更松的H_N。

沿28篇的证书思路，还可以令y_e=α_e/H_d。每个输入集合都满足Σ_{e∈S_i}y_e≤c_i，所以y给出集合覆盖松弛的一个对偶可行解。近似证明中的收费并非任意解释：缩放后，它能提供可独立核对的下界。

保证不等于精确求解

令U={a,b}，三个集合依次为U、{a}、{b}，成本分别为3、1、3。初始比率为3/2、1、3，贪心先买{a}。剩下b时，买U与买{b}都花3，最终成本4；只买U的最优成本为3。

负成本不属于上述保证。收费非负这一步将不再成立，而且最优方案可能主动加入没有新增覆盖的负成本集合。实现拒绝负成本，不能仅把贪心比率算成负数后沿用证明。

朴素教学实现每轮扫描全部q个集合、重新计算与X的交集，至多N轮，预处理后按逐元素成员测试计O(N(L+q))次操作。哈希成员查询按期望常数成本计，集合成本和比率比较的整数位运算另计。这个实现没有声称线性时间，也不依赖堆中的过期比率；后者需要额外设计更新规则。

可复跑检查

接口unweighted_vertex_cover(n, edges)返回顶点集合与极大匹配的原始边索引；weighted_set_cover(universe, sets, costs)返回集合索引。实现位于examples/advanced-algorithms/approx_cover.py，用Fraction比较有理比率，避免浮点平局误差。

1
python3 examples/advanced-algorithms/check_approx_cover.py

本轮实际检查76个穷举图、1885个集合覆盖实例，其中1407个可覆盖、478个不可覆盖；另外对固定种子20260920生成的100个图和100个集合实例进行检查。独立参照枚举所有顶点子集或集合子集，分别核对可行性、2OPT和H_d OPT，使用精确分数比较。

另有空全集、零成本重复集合两个显式边界，6个非法输入拒绝；加权点覆盖反例测得返回成本101、最优1，与适用边界一致。原始结果保存于writing-plans/advanced-algorithms/evidence/approx-cover-results.json。这些有限检查针对教学实现，近似保证来自前面的匹配下界和收费证明。

练习

  1. 构造一条长度为三的路径，改变扫描边的顺序，比较得到的极大匹配和覆盖。说明为什么输出可能不同，但2近似证明不变。
  2. 对U={a,b,c}自行给出四个带非负成本的集合，记录每一步α_e，再核对所有集合的Σα_e≤H_d c(S)。若存在一个零成本覆盖，算法最终总成本应是多少？

参考资料