CSCI3160 L20 k-center最远点贪心与二倍保证

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L20 k-center最远点贪心与二倍保证 · 原件 L20-Approximation-04-k-Center-未核-隐藏.pdf（本地课件） p.1–15 定位：最小化最坏服务距离，利用三角不等式证明最远点策略。

p.1–3：先最小，再最大【新】

p.1 为标题，页脚沿用 Set Cover 不代表本讲还是集合覆盖。p.2 距离为欧氏距离，讲义假设可在多项式时间计算。p.3 一个点到中心集C的距离取最近中心，然后对所有需求点取最坏者：

dist_C(p)=\min_{c\in C}dist(p,c),\qquad pen(C)=\max_{p\in P}dist_C(p).

中心必须从输入P中选，数量恰k，通常假定1≤k≤n。目标不是总距离，也不是每点到最远中心的距离。

p.4–6：控制最差点的代价

图（p.4）：黑点是需求点，c1、c2、c3也是其中的点。元素：p1连接最近中心c2，p2到c1的距离被标为整体pen(C)。看什么：不是中心之间最远的距离决定代价，而是服务最差的需求点到其最近中心的距离。

p.5 指出问题关于n、k为 NP-hard；固定很小k可以枚举 $\binom nk$ ，这不代表关于可变k是多项式。p.6 二倍近似指最终最大服务距离至多2OPT。

p.7–9：每次找离当前中心集合最远的点

p.7 “a point in P with the maximum distC(p)”

先任取一个中心，之后每轮选“最近中心距离”最大者。p.8–9 示意先取左侧c1，再取右侧c2。不能只找离上一次新增中心最远者。维护每点当前最近距离d[p]，新增c时更新为min(d[p],dist(p,c))，扫描取最大，距离运算计常数时总O(nk)、额外O(n)。

p.7 伪代码补齐初始化和合法输出条件：

输入点集合 P，1 ≤ k ≤ |P|
任取 c1 ∈ P；C = {c1}
对每个 p：d[p] = dist(p,c1)
重复 k-1 次：
  在 P 中尚未选取的点里选 d[p] 最大的 c
  C 加入 c
  对每个 p：d[p] = min(d[p],dist(p,c))
返回 C

若不把距离运算视作常数，运行时间应乘上单次距离计算的代价；p.2 仅承诺这个代价为多项式，所以“整体多项式”仍成立。

p.10–12：三次选择怎样形成覆盖

p.10 第三个中心c3落在右侧下方仍服务较差区域；示意图没有坐标，不能由图上像素编造精确距离。p.11 给出二倍定理，p.12 用最优的k个中心划分最优簇。距离并列时指定一个固定的归属规则，才得到互不相交的划分；讲义用“≤所有其他中心”直接定义会使边界重叠，归纳计数时需补这个约定。

补充／数字走一遍。 数字是我为演示取的，讲义没给。共线点坐标0、2、5、9，k=2，先选0，距离为0、2、5、9，第二个选9；更新为0、2、4、0，代价4。最优可选2、9，距离2、0、3、0，代价3；其他中心对不会低于3，所以此次比例4/3，符合二倍界。

补充：把原演示的所有中心对核对完。 对共线点 0、2、5、9，k=2，每对中心的最大最近距离如下：

中心对	各需求点到最近中心的距离	最大值
0,2	0,0,3,7	7
0,5	0,2,0,4	4
0,9	0,2,4,0	4
2,5	2,0,0,4	4
2,9	2,0,3,0	3
5,9	5,3,0,0	5

因此 OPT=3 是枚举六个合法中心对所得，而不是仅凭找到一个代价 3 的方案就宣布最优。这也展示了维护数组时为什么取 min：新增 9 后，点 2 的距离仍是到 0 的 2，不能被到新中心的 7 覆盖成更差值。

自测：k=n 与“当前最大距离已为 0”怎样处理？

所有点都选为中心时每点距离 0。若不同输入记录坐标重合，可能在未选够 k 个记录时最大距离已经为 0；继续任意选不同的未选记录即可满足数量约束，代价仍为 0。实现需防止重复选择同一条记录。二倍不等式在 OPT=0 时仍有意义，但不能再用输出除以 OPT 来计算数值比例。

p.13–15：两种情况都用同一个半径

p.12 令最优中心为 $C^*=\{c_1^*,\ldots,c_k^*\}$ ，把每个点分配给一个最近中心，得到 $P_i^*$ 。于是对任意 $p\in P_i^*$ ：

dist(p,c_i^*)=dist_{C^*}(p)\le pen(C^*)=OPT.

p.13 若算法每个最优簇都取了一个中心c，那么同簇任意p经最优中心转折，距离至多OPT+OPT=2OPT。

这一情况的逐点不等式为

dist_{C_{ours}}(p)\le dist(c,p)\le dist(c,c_i^*)+dist(c_i^*,p)\le2pen(C^*).

再对所有 p 取最大，才得到整体 penalty 的上界。

p.14 若漏了某个最优簇，k个所选点放进不到k个簇，必有两个ca、cb同簇，所以它们距离≤2OPT。p.15 设cb后选，考察它被选前的中心集C。它当时最远，而ca已在C中，因此对任意p有

dist_{C_{ours}}(p)\le dist_C(p)\le dist_C(c_b)\le dist(c_a,c_b)\le2OPT.

第一步来自增加中心只会降低最近距离，第二步来自贪心最远，第三步来自ca是可选的一个中心。三步缺一不可，不能仅凭“同簇两点近”就直接断言所有点都近。原文p.15“c2 was the next point picked”应读作cb，和前后定义一致。

本讲核心考点

（C 级通识）区分 k-center 的最大最近距离与总距离目标。
（C 级通识）维护最近距离实现最远点选择。
（C 级通识）用最优簇、抽屉原理、三角不等式证明二倍界。

附录

本讲所需过程已在正文展开。

来源与证据

本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。
原件：L20-Approximation-04-k-Center-未核-隐藏.pdf（本地课件）；页码均为 PDF 页号。
版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。
发布状态（2026-09-17 核验时）：官网链接所在行隐藏，当时按预习参考处理；不据此推断后续发布或考试范围。
既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无
缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。