CKR 随机球划分 | Codeboy's Blog

在五个共线点 $0,1,2,3,4$ 上画半径 $3/2$ 的球，先处理中心 $2$ ，它会领取 $1,2,3$ ；随后中心 $0$ 只领取 $0$ ，中心 $4$ 只领取 $4$ 。三个块都很小，但相邻点 $0,1$ 被拆开。改变中心顺序就能改变这条边界。CKR 划分把半径与中心顺序随机化：每一次输出都限制块的大小，再对事先固定的近点给出被拆开的概率界。

形式陈述

完整采样合同

给定有限度量空间 $(X,d)$ 和尺度 $\Delta>0$ ，令 $n=|X|$ 。独立抽取一份均匀随机排列 $\pi$ 和均匀实数

R\sim\operatorname{Unif}[\Delta/4,\Delta/2).

按 $\pi(1),\ldots,\pi(n)$ 依次处理所有中心；中心 $z$ 领取尚未被领取且满足 $d(z,x)\le R$ 的点，非空领取集成为一个块。等价地，每个点的主人是排列中第一个能覆盖它的中心。这个单尺度算法通常称为 Calinescu–Karloff–Rabani（CKR）划分。[1, Algorithm1]

本页闭球采用 $\le$ ；连续分布下有限个边界半径的概率为零，但固定随机带的可复现执行仍必须保留这条约定。中心即使早已被领取，也继续处理。球心可以不属于它最终领取的块，因此不能把“主人”理解成一定驻留于块内的代表。

对每个固定输入，随机性只来自 $\pi,R$ ，这是随机算法的固定输入口径。给定这两份数据后，流程完全确定；伪随机种子的若干次实验不是概率定理。空集输出空划分，不需要谈其中心；以下概率界只对 $n\ge1$ 的固定非空集合使用。

两种保证

每次输出都是 $X$ 的划分，每块在原度量中的直径至多 $\Delta$ 。对任意事先固定的非空 $S\subseteq X$ ，记 $H_n=\sum_{j=1}^n1/j$ ，则

\Pr[S\text{ 未包含在同一块中}] \le\min\!\left\{1,\frac{4H_n\operatorname{diam}(S)}{\Delta}\right\}.

特别地，对固定点对 $u,v$ ，拆开概率至多 $\min\{1,4H_nd(u,v)/\Delta\}$ 。对固定闭球 $B(x,t)=\{y:d(x,y)\le t\}$ ， $t\ge0$ ，三角不等式给其直径至多 $2t$ ，所以

\Pr[B(x,t)\subseteq P(x)] \ge\max\!\left\{0,1-\frac{8tH_n}{\Delta}\right\}.

$P(x)$ 表示包含 $x$ 的块。这是一个 padding 保证：以一定概率，点周围的小球整个留在它所在的块里。它不是对所有点同时成功的断言，也没有声称块数最少。文献还给出更精细的局部体积比界；本页只使用并完整证明上述调和界。[1, §2]

直觉

两种随机性各解决一件事。半径平移球的边界，使两个很近的点只有在一小段半径范围内才会落在球的两侧；随机顺序使许多潜在中心竞争，避免把每个危险球都当成必然发生的切割。

为什么要同时考虑“能切开”与“最先到达”？一个很晚的中心可能把小集合横切得很厉害，但若集合早已完整交给前面的中心，它就没有影响。证明只向第一个触及集合的中心记账；越晚才开始有机会触及的中心，前面已有越多竞争者，其成为第一名的概率就越小。

星图中先处理叶点零，再处理已经被领取的中心一点；留下的两个叶点属于同块但诱导子图断开 — 所有中心都参与与弱直径

划分与直径为什么始终正确

每点至少会被以自身为中心的球覆盖，所以最终全部被领取。领取时只允许尚未被领取的点，故不同块互不相交。若 $u,v$ 同属中心 $z$ 领取的块，则

d(u,v)\le d(u,z)+d(z,v)\le2R<\Delta.

即使 $z$ 不在块内，这条原度量不等式仍然有效。若把半径右端也包含进来，结论改成 $\le\Delta$ ，其余证明不变。

给最早触及者一个精确概率

固定 $S$ 。对每个中心 $z$ ，计算

a_z=\min_{x\in S}d(z,x),\qquad b_z=\max_{x\in S}d(z,x).

$a_z$ 是球首次触及 $S$ 的半径， $b_z$ 是球已经覆盖整个 $S$ 的半径。若 $a_z\le R<b_z$ ，球只覆盖其中一部分；这段危险区间长至多 $\operatorname{diam}(S)$ ，因为取得最小和最大的两点也相距不超过这个直径。

按 $a_z$ 非降排列所有中心为 $z_1,\ldots,z_n$ ，相等处固定任意顺序。这是用于证明的距离次序，与随机处理顺序 $\pi$ 不同。先固定 $R$ ：若 $a_{z_j}\le R$ ，则前 $j$ 个中心全部能够触及 $S$ 。要让 $z_j$ 成为最先触及者，至少要求它在这 $j$ 个中心中排列最靠前，概率为 $1/j$ ；还可能有更多竞争者，所以这是上界。它依赖排列在固定半径条件下仍均匀，即两个随机量独立。

$S$ 被拆开当且仅当最早触及它的中心只覆盖其中一部分。若该中心覆盖全部， $S$ 同时被领取；若只覆盖部分，剩余点不可能日后再次归到同一个中心，因为每个中心只处理一次。因此不同中心的“最早且只覆盖部分”事件互斥，积分给出

\begin{aligned} \Pr[S\text{ 被拆开}] &\le\sum_{j=1}^n\frac1j\frac4\Delta \left|[a_{z_j},b_{z_j})\cap[\Delta/4,\Delta/2)\right|\\ &\le\frac{4\operatorname{diam}(S)}\Delta\sum_{j=1}^n\frac1j. \end{aligned}

竖线在这里表示实区间长度。也可把每个中心的贡献写成指示变量，再用期望的线性性相加；不需要假设这些贡献相互独立。最后再与概率平凡上界 $1$ 取小。

例子与边界

五点上的固定执行和精确分布

仍用 $X=\{0,1,2,3,4\}$ 、 $d(u,v)=|u-v|$ ，取 $\Delta=4$ 、 $R=3/2$ ，中心顺序为 $(2,0,4,1,3)$ 。中心 $2$ 先领取 $\{1,2,3\}$ ，中心 $0$ 领取 $\{0\}$ ，中心 $4$ 领取 $\{4\}$ ；最后两个中心没有新点可领。按点身份列出的主人数组为 $(0,2,2,2,4)$ 。

现在恢复真正分布：排列在 $120$ 种中均匀选， $R$ 在 $[1,2)$ 均匀选。因为所有非零距离是整数，除概率零的边界外，每个球始终恰含距离至多 $1$ 的点，半径在这个例子中不再改变单尺度结果。

点 $0,1$ 的候选中心为 $\{0,1,2\}$ ，其中中心 $0,1$ 都覆盖两点，只有中心 $2$ 只覆盖点 $1$ 。最先出现者均匀，所以分离概率是 $1/3$ 。点 $1,2$ 的候选中心为 $\{0,1,2,3\}$ ，中心 $0,3$ 各只覆盖一端，故分离概率是 $1/2$ 。同样长度的一对，周围候选中心不同，实际概率可以不同。

闭球 $B(2,1)=\{1,2,3\}$ 的候选中心是全部五点，其中只有中心 $2$ 同时覆盖三点。因此保留完整小球的概率是 $1/5$ ，失败概率是 $4/5$ 。这里通用界 $8H_5/4$ 大于 $1$ ，只能给平凡结论；不能为了让例子漂亮而删掉上界中的尺度条件。

弱直径不保证内部可达

考虑星图，中心为 $1$ ，三片叶为 $0,2,3$ ，每边长度 $1$ 。使用最短路度量，取 $R=1$ 和处理顺序 $(0,1,2,3)$ 。中心 $0$ 先领取 $\{0,1\}$ ；中心 $1$ 虽已被领取，仍继续处理，并把 $\{2,3\}$ 领为第二块。

第二块的原图距离为 $d(2,3)=2$ ，这称为弱直径；原图中的短路经过块外点 $1$ 。由 $\{2,3\}$ 诱导的子图没有边，两点内部不连通，所以其强直径可记为无穷。此例同时说明，跳过“已经归属于某块的中心”会改变 CKR 分布：那样 $2,3$ 会各自成为单点块。

中心顺序、最近中心与块数

主人是第一个覆盖者，不是最近者。例如上述星图中的点 $1$ 到自己距离零，却属于中心 $0$ 的块。改成最近中心规则会产生另一种划分，原来的最先触及概率不再描述新算法。

本算法也没有中心预算 $k$ 。若尺度比最小正距离还小，每点单独成块；若半径超过全空间直径，第一个中心就领取全部点。需要恰好或至多 $k$ 个中心时，可读最远点优先 k-center，它控制覆盖半径并给分离下界，目标与本页的随机边界不同。

推论与应用

固定加权点对的切割成本

给每个点对一份事先固定的非负权重 $w_{uv}$ 。将跨块权重相加为 $W_{\rm cut}$ ，由线性性有

\mathbb E W_{\rm cut} \le\frac{4H_n}{\Delta}\sum_{u<v}w_{uv}d(u,v).

这不要求不同点对的分离事件独立。如果看见输出以后才把全部权重放到一条被切开的短边上，权重已依赖随机结果，上式证明不再适用。

单尺度划分还可用于多尺度层级。不同尺度独立得到的块，甚至使用同一排列与缩放半径得到的块，也未必天然嵌套；FRT 树嵌入必须与上一层共同细化，并对跨尺度贡献重新记账。单层的调和概率界不能直接乘层数后宣称已经得到无尺度依赖的伸长界。

真实实现成本

给定随机带后，直接扫描每个中心与每个尚未领取的点，最坏为 $O(n^2)$ 次距离查询，主人数组和全部块的点成员总计 $O(n)$ 空间。排列校验可用长度 $n$ 的标记数组线性完成；附件为保持接口简短采用排序校验，另需 $O(n\log(n+1))$ ，在非空输入的二次上界内。若保留每轮的完整主人快照，日志还可能达到 $O(n^2)$ ，本页附件只保留最终分块。

完整距离矩阵另占 $O(n^2)$ ，三角检验另需 $O(n^3)$ 。若每次由距离 oracle 计算，查询成本需乘相应单次费用；从稀疏图获得全部点对距离的成本也不能省略。Mendel–Schwob 给出了不用预存全矩阵的稀疏图加速，[1, §3] 但其 Dijkstra 记录最小值维护不是这里这段双循环的复杂度。

均匀实数是概率模型。对有理矩阵的小例，附件枚举半径阈值之间的区间，区间内流程不变，便能用区间长度精确积分。枚举全部排列需阶乘时间，仅用于终点的分布核验，不能当作大规模采样器。

参考资料

Manor Mendel、Chaya Schwob，Fast C-K-R Partitions of Sparse Graphs，arXiv:0809.1902v2，2009；Algorithm1（PDF第2页）给出本页单尺度采样，§2 的 Lemma2.1 给更强 padding 结果，§3 讨论稀疏图加速。本页调和界在正文独立推导。
Jittat Fakcharoenphol、Satish Rao、Kunal Talwar，A Tight Bound on Approximating Arbitrary Metrics by Tree Metrics，STOC2003，§§1.3、2.3，pp.449–452：CKR 型划分、最先触及中心与距离区间记账。

形式陈述 ​

完整采样合同 ​

两种保证 ​

划分与直径为什么始终正确 ​

给最早触及者一个精确概率 ​

五点上的固定执行和精确分布 ​

弱直径不保证内部可达 ​

中心顺序、最近中心与块数 ​

固定加权点对的切割成本 ​

真实实现成本 ​

反向链接