最远点优先 k-center

选一个中心后，最该担心的是仍离所有中心很远的地点。把它变成新中心，会把某些最近距离降低，其他最近距离不变，因此覆盖半径单调不增。不过，“修补当前最坏点”还不足以证明近似：关键是这些被选中的点同时记录了此前各轮的困难。

假设最后还剩一个距离 $R$ 的点。后选中心在入选时比它早的中心都至少离这么远，否则当时最大的最近距离就不可能最终仍有 $R$。因而中心连同最后的最远点形成 $k+1$ 个彼此分离的地点。任何只开 $k$ 个站的方案，都必须让某一站同时负责其中两个；三角不等式把这两个地点的间距变成该站覆盖半径的二倍下界。

两个方向都要核验 ​

最近距离数组的归纳很直接。第一中心加入后，$D[x]=d(x,c_1)$。若更新前 $D[x]=\underset{c\in C_j}{min}d(x,c)$，再与 $d(x,c_{j+1})$ 取小，恰是对 $C_{j+1}$ 的最小值。因此最终指派确实覆盖所有点，半径不会因为漏看某中心而报大或报小。

再记第 $j$ 轮覆盖半径为 $R_j$。数组只会下降，所以 $R_1\ge \cdots \ge R_k=R$。任取 $a<b\le k+1$，在 $c_b$ 被选为最远点时，

这里 $c_{k+1}$ 只作见证，并不增加实际站点数。把 $k+1$ 个见证指派给任意最优的 $k$ 个中心，至少两点 $u,v$ 共用一个中心 $c$。于是

这同时证明 $R/2\le R^{\ast }\le R$。当 $k=n$ 时全体点都是中心，$R=R^{\ast }=0$，无需构造不存在的第 $n+1$ 点。

把五点例子算到底 ​

按身份 $0,1,2,3,4$ 排列，初始中心取 $0$。执行过程为：

最近中心身份为 $(0,0,0,4,4)$；中点平局留给旧中心 $0$。半径 $R=2$，见证 $\{0,4,2\}$ 的三组距离是 $4,2,2$，所以任何两个中心的最优半径至少为 $1$。方案 $\{1,3\}$ 达到 $1$，故二倍损失在这个实例上恰好取等。附件枚举中心组合时按身份序返回另一个同样最优的方案 $\{0,3\}$。

证书与算法轨迹承担不同任务。验证输出的 $k$ 个中心、全部指派距离不超过 $R$，并检查 $k+1$ 个见证的所有点对距离至少为 $R$，已经足以证明二倍近似；这份验证器无需重跑贪心。若还声称“这就是指定起点和并列规则的运行”，才需要逐轮核最大者。

半径与簇直径差在哪里 ​

半径为 $R$ 的中心指派使每个簇的直径至多 $2R$，因为簇内两点都能经由中心连接；但直径可能小于这个上界。对另一目标“把 $X$ 分成 $k$ 个非空簇，最小化最大簇直径”，上述 $k+1$ 个见证给出的下界是 $R$：同簇的两点本身就相距至少 $R$。结合算法簇直径至多 $2R$，也得到二倍近似，却是另一套上下界。不能对中心半径直接宣称最优值至少为 $R$，五点例子已经否定它。

改输入合同会发生什么 ​

若把中心放到点集外，有限矩阵没有提供到那些位置的距离。二维连续的一中心问题可由最小包围圆理路最小包围圆Minimum enclosing circle · Smallest enclosing disk · Welzl algorithm · Welzl 最小圆算法用至多三个边界点核验最小圆，并以强制边界的随机递归在期望线性算术时间内构造它。求解；它使用坐标和几何支持点，输出的中心甚至不是输入点。本页的程序只返回原点身份，不自动解决受限设施集、连续平面或带容量版本。

若使用平方距离，二倍因子也会变化。数轴 $0,1,2$ 上，平方距离矩阵满足 $d(0,2)=4$ 而 $d(0,1)+d(1,2)=2$。选一个中心并从 $0$ 开始，半径为 $4$，最优中心 $1$ 的半径为 $1$，已超过二倍。失败发生在三角不等式，不是并列规则。

固定预算与固定尺度互相读取 ​

覆盖数与 packing理路度量熵与覆盖数Metric entropy · Covering number · 覆盖数在指定尺度和度量下，用有限网覆盖函数类，并以覆盖数或度量熵量化其有效大小。把半径固定，询问要多少中心；k-center 把中心数固定，询问需要多大半径。最远点序列可以同时给出这些尺度的信息：持续加入最远点，直到覆盖半径不超过给定 $\epsilon$，所得中心是一个内部 $\epsilon$-cover；除第一点外，每次入选时距离旧中心严格大于 $\epsilon$，所以这些中心也形成严格 $\epsilon$-packing。

这不表示其中心数最少。它说明每个入选点都有“此前所有中心都覆盖不到我”的理由，从而把覆盖的可行性与分离的必要性连在同一条序列上。若把终止条件改成严格小于 $\epsilon$，packing 的边界不等号也要相应改变。

时间、存储与输入验证 ​

每轮扫描 $n$ 个点更新距离，再扫描取最大值，$k$ 轮为 $O(nk)$ 次距离访问与比较，工作数组和输出中心共 $O(n+k)$ 空间。证书验证可直接检查 $n$ 份指派和 $(\genfrac{}{}{0ex}{}{k+1}{2})$ 个见证点对，需 $O(n+k^2)$ 次访问。附件另做穷举最优对照，代价为 $O((\genfrac{}{}{0ex}{}{n}{k})nk)$；这不属于贪心算法的运行界。

这些界把一次距离查询视为单位操作。若距离由 oracle 提供且一次成本为 $T_d$，查询部分乘 $T_d$；若预先存完整矩阵，输入本身另占 $\mathrm{\Theta }(n^2)$。读入并验证方阵、正定性和对称性需 $O(n^2)$，穷尽三角不等式需 $O(n^3)$，不能算进免费的输入承诺。精确有理数的比较还须计入分子分母位长。

有限度量单元终点继续使用这五个点：固定中心预算给覆盖，固定尺度给随机块，再把多尺度块组织成树。三种输出的半径、块数与距离保证分别核验。