CSCI3160 Regular 13：Hitting Set、Set Cover 与 k-center

原件：题目（本地课件）；官方答案（本地课件） p.1–3。定位：区分“选元素命中集合”与“选集合覆盖元素”，并把最远点贪心推广到图度量。

Problem 1：Hitting Set 转为 Set Cover（答案 p.1）

原问题给一族集合 S₁,…,Sₘ，允许从元素宇宙 U 中选 H，使每个 Sⱼ 至少含一个被选元素。新问题的 universe 是原集合的编号 1,…,m；对每个原元素 e，建 Cₑ={j:e∈Sⱼ}。

选 e 就相当于选 Cₑ；每个原集合被命中，等价于每个编号被覆盖，选择数量不变。因此最优解也对应。若原集合为空，则该编号无候选能覆盖，应报告无解。

自取 S₁={a,b}、S₂={b,c}：新集合 Cₐ={1}、Cᵦ={1,2}、C꜀={2}。选 Cᵦ 覆盖两个编号，映回 hitting set {b}。记录原元素身份，避免集合内容相同导致映射丢失。

原问题是从 S₁,…,Sₘ 中选一些覆盖 U。现在把集合编号 1,…,m 当作可选元素；对每个原元素 e 创建约束集合 Hₑ={j:e∈Sⱼ}。选择编号集合 J 命中每个 Hₑ，等价于每个原元素至少被某个选中的 Sⱼ 覆盖。

例如 U={a,b,c}，S₁={a,b}、S₂={b,c}，新约束为 Hₐ={1}、Hᵦ={1,2}、H꜀={2}。必须选编号 1 和 2，映回两个原集合。注意 Q1 与 Q2 都在转置“元素属于集合”的关联表，但输出到底是集合还是元素不同，不能只写“对偶一下”而不说明宇宙。

两种构造都只需遍历原关联关系，总输入大小多项式，且保持解的基数。

按 Q1 归约，新 universe 大小是原集合数 m。对新实例用贪心集合覆盖，获得大小≤(1+ln m)OPT 的解，再映回对应原元素。两边最优值相等、输出大小相同，因此近似比原样保留。

不能把界误写成 1+ln|U|：覆盖分析的分母规模是“需要满足多少条集合约束”，而非“有多少候选元素”。原集合族为空时最优为空，单独返回；有空集合则无解，不能对无解实例谈有限近似比。

先计算所有顶点对最短距离。对非负权无向图，可从每点跑 Dijkstra，或用多项式的全点对算法。然后任选第一个中心，反复选“距当前最近中心最远”的未选顶点，直到 k 个。

设算法覆盖半径为 r，再取一个距最终中心集合最远的点 q。已选 k 个中心加 q 共 k+1 点，它们两两距离至少 r：每个后来中心在选入时距离此前中心至少最终半径，q 亦然。最优 k 个中心以半径 R 覆盖它们，鸽巢原理使其中两个属于同一个最优中心，三角不等式给两点距离≤2R。因此 r≤2R。

最短路满足三角不等式，因为拼接 u 到 c、c 到 v 的路线提供一条 u 到 v 的候选游走。零边使不同点距离可为零，不影响证明，只需保证每次选不同顶点。

原图可能不连通。 若连通分量数超过 k，任何 k 中心解都留下一个分量没有中心，OPT=∞。若分量数≤k，最远点贪心在存在未覆盖分量时会优先选距离∞的顶点，因此最终每个分量至少一个中心，之后在有限距离内同样成立。不能默认原题未给的连通性。

补充：k+1 点证明里的零半径边界。 若最终半径r>0，最远点q不可能已经是中心（中心到自身距离0），因此确有k+1个不同点，抽屉论证可直接使用。若r=0，则所需结论r≤2OPT已经因OPT非负而成立，无须强找一个不同于全部中心的q；特别k=n时根本没有未选点。

在有限半径情形，后来选入的中心c到此前中心集合的距离是当时的最大最近距离，随着添加中心这个最大值只会下降，所以不小于最终r。于是对每个较早中心a都有dist(a,c)≥r，不是只与“上一个中心”距离大。这个两两分离性质才够支撑抽屉原理。

自测：为什么用平方距离做比较，不能在证明里也直接套平方距离三角不等式？

共线点0、1、2的平方距离有D(0,2)=4，而D(0,1)+D(1,2)=2，三角不等式失败。比较顺序相同保证选出的中心不变；近似证明应继续用真实距离，最后若平方化目标才把二倍变成四倍。

二维欧氏距离比较可改用平方距离

D(p,q)=(p_x-q_x)^2+(p_y-q_y)^2.

平方根在非负数上严格递增，所以“对中心取最小，再对点取最大”的选择次序不变。维护每点到最近中心的平方距离，新中心加入时取 min；选中心时找最大 D。输出中心集合即可，无需把半径的平方根写成精确小数。

自取 p=(0,0)、q=(3,4)、r=(1,5)，距离平方分别为 25、26，直接知道 r 更远，不需要算 √26。近似比仍是对真实欧氏半径的 2；若讨论平方目标，比值对应为 4，不能说平方距离也满足相同的三角不等式。

坐标需有有限编码，例如整数或有理数。课程 RAM 模型内这些运算可视常数；严格位复杂度中是输入位数的多项式，并非对任意巨大数都 O(1)。

假设有多项式算法 A：给定点集及阈值 r，返回使覆盖半径≤r 的最少中心数与中心集合。因为中心限制从输入点中选，任意中心集合的覆盖半径一定是某对输入点的距离，或 0。

列出 O(n²) 个候选距离，去重并排序。对候选 r 调用 A，检查最少中心数是否≤k。这个谓词随 r 增大只可能从假变真，因为旧解在放宽半径后仍可行。找第一个真值（逐个试已是多项式，也可二分），获得最优 k-center 半径；若返回少于 k 个中心，任意补充不同输入点到 k 个，半径不会增加。

为什么真是最优？最优 k-center 自己的半径必在候选列表里，该阈值一定可用≤k个中心覆盖，所以首个真值不大于最优半径；反过来，首个真值返回的解补齐后就是合法 k-center，不可能比最优更小。两个方向夹出相等。

对互异点，k=n 时半径0直接处理；k<n时最优半径为正，可符合题面 r>0 的接口。重合点若保留成不同记录，可先按位置处理零半径情况。所谓“固定 r”按官方意图是 r 作为给定阈值的统一算法；若特指某个预设正有理常数，也可按比例缩放坐标把任意阈值转成该常数。

于是 A 会导出精确 k-center 的多项式算法，和课程使用的 k-center NP 难前提冲突，除非 P=NP。此处困难性前提来自题目给定的课程背景，不由上述归约凭空证明。官方把首个解 cost 直接写成候选 r，严格说先有≤r，再由最小性证明等号；还需补齐到恰好 k 个中心。

官方题目及答案 p.1–3。本文补充不连通图、零距离、有限坐标编码以及“至多 k”补成“恰好 k”的边界。