CSCI3160 Regular 12：集合覆盖归约与区间刺点

原件：官方题解合卷（本地课件） p.1–2，包含全部四题的题面。 来源限制：单独题目 PDF 链接返回零字节，因此使用此官方合卷，不伪造题目文件。 定位：准确选择 universe 与候选集合，并证明可行性、目标值和规模都保持。

Problem 1：顶点覆盖归约为集合覆盖（合卷 p.1）

输入图 G=(V,E)。将边当作新宇宙 U，而不是顶点；为每个顶点 v 创建带身份标签的集合 Sᵥ，包含所有与 v 相接的边。

选若干顶点能覆盖每条边，当且仅当对应的 Sᵥ 之并覆盖 U。一方向：边被集合覆盖意味着至少一个端点的集合被选；另一方向：边有被选端点，就在该端点集合内。因此可行解双向映射，且选择的顶点数与集合数相同，最优值也相同。

自取路径 a–b–c：U={ab,bc}，Sₐ={ab}、Sᵦ={ab,bc}、S꜀={bc}，最优集合覆盖选 Sᵦ，映回顶点 b。

集合中总元素出现次数是 2m，构造线性，调用假设的多项式最优集合覆盖算法后再映回即可。不同顶点的集合内容可能相同，要保留顶点标签；不能把相同集合合并后丢失对应关系。归约方向是“用集合覆盖求解器解决顶点覆盖”，所以顶点覆盖困难性传给集合覆盖，不能把方向说反。

Problem 2：尚未选过的最优集合提供更强平均收益（合卷 p.1–2）

算法正要选第 i 个集合，说明还有 z>0 个元素未覆盖。令 C 是已经选到的、恰好属于某个固定最优解 C★ 的集合。

若 C=C★，最优解的所有集合已经在已选集合里，宇宙早就覆盖完，不会有第 i 步，矛盾。因此 C★\C 非空，下面的除法分母不会为零。

所有剩余元素必须被 C★\C 覆盖：C 中集合已选，若剩余元素属于它们，早已被覆盖。设 r=|C★\C|，这些 r 个集合的剩余收益之和至少 z（重复覆盖只会增加这个和）。所以至少一个收益≥z/r，否则总和<z。贪心挑最大收益，选出的 Sᵢ 也至少有这个收益。

自取剩余 7 个元素、未选最优集合 3 个，至少一个覆盖≥7/3，整数上至少 3 个。这里无需各集合覆盖的剩余元素互不相交；平均论证只要求总和不小于并集大小。

Problem 3：只能选给定点的区间刺点（合卷 p.2）

把每个待刺区间当作宇宙中的一个元素；对每个候选点 p，建立集合 Iₚ，包含所有覆盖 p 的区间。选点集合击中所有区间，等价于对应集合覆盖所有区间，数量相同。

先检查每个区间至少包含一个候选点；若有区间一个点也不含，原问题无可行解，不能把它从 universe 里悄悄删掉后声称已完成刺点。题目有有限 OPT 的意图时意味着这个条件成立。

对宇宙大小 n 的集合覆盖运行最大新覆盖数贪心，返回点数≤HₙOPT≤(1+ln n)OPT。一个简单多项式实现预建 n×n 包含关系，每轮扫描所有候选点计算收益、最多选 n 次，O(n³) 已满足题目。

自取区间 [1,3]、[2,5]、[6,7]，候选点 2、4、6。点 2 的集合含前两个区间，点 4 只含第二个，点 6 含第三个。先选 2，再选 6，得到刺点集 {2,6}。

近似界为何是对数。 当还剩 z 个区间，OPT 个最优候选点总能覆盖它们，至少一个收益≥z/OPT；贪心不差于它。等价地把每轮成本 1 平摊给该轮新覆盖元素，第 j 个从后往前被覆盖的元素收费至多 OPT/j，总收费≤OPT·Hₙ。它计的是约束数量 n，而不是坐标范围。

Problem 4：允许任意实数点时如何离散化（合卷 p.2）

虽然候选点无限多，但可将任意一个最优刺点 p 移到它所击中区间的最小右端点 r。对其中每个区间 [lᵢ,rᵢ]，有 lᵢ≤p≤r≤rᵢ，因此移动后仍击中所有原先击中的区间。若 p 没击中任何区间，则直接丢弃它。逐点移动后，存在一个最优解全部选在原区间右端点中。

因此只需 n 个右端点（官方取所有 2n 个端点也正确），按 Q3 建集合覆盖实例，得到同样对数近似，规模仍多项式。闭区间端点算作命中；若换成开区间，移动到端点这步需要重新处理。

补充：本题其实可精确贪心。 按右端点递增，遇到未被已有点刺中的区间，就选其右端点。对当前最早结束的未覆盖区间，任何最优解都必须在其中放一个点，将该点右移到当前右端点，不会丢掉尚未处理区间的命中关系；于是可以交换成包含此选择的最优解。递推完成，得到最优刺点集，排序 O(n log n)。这个更强结论可作理解补充，但原官方路线只需离散化加集合覆盖近似。

补充：精确区间贪心的交换只保护尚未处理的约束。 选当前最早右端点r，其区间I必须被某个最优点p击中，故p≤r。对任一仍未处理且被p击中的区间J，其右端点不小于r，而左端点≤p≤r，所以把p右移到r仍命中J。已处理区间已有先前选点负责，不需要这次替换点继续兼顾它们。这个时间顺序解释了为何任意右移并不都安全。

来源与证据

官方 Ex12 答案合卷 p.1–2。单独题目原件不可下载不影响四道题的完整读取。本文明确补齐 Q3 的可行性检查和 Q4 端点替换证明。