@@M@@k@@-median结果族 125：The metric
@@M@@k@@-median approximation threshold and recovery · 学科：Theoretical computer science · 验证状态：主结果已 Lean 形式化
在一条长街上开连锁店:从候选地址里挑至多 @@M@@k@@ 家,让每位顾客走到最近门店的总路程最短——这就是 @@M@@k@@-中值。老方法的通病是:要么偷偷多开店,要么总路程压不进”最优的两倍”。这篇论文打磨出两件新工具,第一次让一个”绝不多开一家店”的随机算法把总路程做到严格优于 2 倍最优。
关键词卡片
@@M@@k@@-中值(metric k-median):选至多 @@M@@k@@ 个设施,最小化所有客户到最近设施的距离总和。看个具体例子
图中草稿解把两家店挤进第 1 簇、漏掉第 3 簇;恢复算法认出坏簇后重摆,总路程从 31 降到 5。主定理:在任意有限有理度量上,随机算法总是开至多 @@M@@k@@ 家店,费用 @@M@@\le(2-\sigma)\times@@最优(@@M@@\sigma>0@@ 为绝对常数),概率与期望意义下同时成立;修复过程的中间保证是 @@M@@1+2/e+\varepsilon\approx1.736@@。
为什么值得关心
@@M@@k@@-中值的近似比三十年来从 @@M@@3+\varepsilon@@ 一路降到 @@M@@2+\varepsilon@@,但”严格小于 2 且绝不多开店”始终无人做到;本文跨过这条线,而且是本结果族中验证等级最高的一篇。
已 Lean 形式化
第一级台阶
导读的”连锁店选址”翻译成半数学语言：对象是客户位置集与候选店址集，外加满足三角不等式的两两距离；操作是从候选地址里挑至多 k 家开店，每位客户走向最近的一家；目标是所有人的总路程最短。论文的两件工具也各对应场景一角：从一份”草稿选址”修补无人照看的片区（恢复），以及一本保证花销严格低于对手的账本（支付论证）。
第二级台阶
精确化关键概念：费用 cost(S) 定义为客户到所选设施最近距离之总和，最优值记 opt_k；锚点是规模为 h 的现成可行解；把一个假想的比较解按最近设施分簇，能在此锚点中找到互异”代理”设施的簇称好簇，其余为坏簇，代理指派总费用须控制在好簇费用加一个小比例的误差。对数剩余指 CGLSS 构造允许带 O(log N) 个免费副本，最后须折算回真实设施。
第三级台阶
两条定理站在这些概念上。恢复定理：在距离为多项式有界正整数的归一化度量上，若坏簇数至多 L₀ log N，随机算法以对坏簇数单指数、对规模多项式的时间输出不超过 h 个设施，费用达 (1+2/e+ε)P，概率至少 1−ζ——比较解、分簇与代理只存在于分析中，算法一概不知，这个”存在即可用”的承诺挡住了无从下手的乱局；归一化假设则挡住任意大距离导致的舍入失控。支付定理（有界价格严格性）：对剩余构造的一次相容执行，客户预算之和被压到 λ+(2−c(T)/2)P_C，凿开 2 倍的缺口。二者合并：存在绝对常数 σ>0，随机算法在任意有限有理度量上每个输出都开至多 k 家店，费用不超过 (2−σ)·opt_k，高概率与期望意义同时成立。
本文为度量 @@M@@k@@-中值（metric @@M@@k@@-median）问题打造两件工具：坏簇数仅为对数时仍可多项式完成的”锚点恢复”算法，以及对剩余构造一次相容执行的”有界价格严格性”支付论证；合并后首次在一般有理度量上得到严格小于 2 的随机 @@M@@(2-\sigma)@@-近似。
度量 @@M@@k@@-中值问题给定客户集 @@M@@D@@、候选设施集 @@M@@F@@、整数 @@M@@k@@ 与度量距离，要求选至多 @@M@@k@@ 个设施 @@M@@S@@ 最小化 @@M@@\operatorname{cost}(S)=\sum_{p\in D}d(p,S)@@。它是聚类与设施选址理论的核心模型：LP 舍入（Charikar–Guha–Tardos–Shmoys）、原始-对偶方法（Jain–Vazirani）、对偶拟合与交换局部搜索（Arya 等，@@M@@3+\varepsilon@@）先后给出常数因子；Li–Svensson 的伪近似约化与后续 bi-point 舍入推进到 2.675、2.613，Cohen-Addad–Grandoni–Lee–Schwiegelshohn–Svensson（CGLSS，STOC 2025）达到 @@M@@2+\varepsilon@@。真正的拦路虎是”设施预算”：允许少量额外设施的松弛解容易构造，而每个输出都严格开至多 @@M@@k@@ 个设施、同时把费用压到 2 以下，此前没有分析能做到。本文在 CGLSS 架构上补齐两块短板：恢复步对例外簇数的依赖降到单指数，支付步与一次实际执行的预算完全相容。
其一，精化恢复定理：在距离为不超过 @@M@@N@@ 固定多项式界的正整数的归一化度量上，设锚点（anchor）@@M@@S@@ 有 @@M@@h@@ 个设施，若存在同规模比较解 @@M@@O@@（费用 @@M@@P@@），其簇分为好簇与坏簇（bad center），好簇各有 @@M@@S@@ 中互异代理（proxy），代理指派总费用至多 @@M@@P_g+\mu P@@（@@M@@\mu\le\min\{1/4,\varepsilon/12\}@@），坏簇数 @@M@@m\le L_0\log N@@，则只输入 @@M@@S,\mu,L_0,\zeta@@ 的随机算法恒有 @@M@@|\widehat S|\le h@@，且以概率至少 @@M@@1-\zeta@@ 达到 @@M@@\operatorname{cost}(\widehat S)\le(1+2/e+\varepsilon)P@@，时间对 @@M@@m@@ 单指数、对 @@M@@N@@ 多项式。其二，有界价格严格性（bounded-price strictness）：对 CGLSS 对数剩余构造的一次相容执行，若常规开设支付 @@M@@\lambda\le TP_C@@，则 @@M@@\sum_{p\in C}\alpha_p\le\lambda+(2-c(T)/2)P_C@@，@@M@@c(T)>0@@。其三，全局应用：存在绝对常数 @@M@@\sigma>0@@，使任意有限有理度量上的随机多项式算法总开至多 @@M@@k@@ 个设施，以至少 @@M@@1-(|D|+|F|+2)^{-a}@@ 的概率且在期望意义下费用 @@M@@\le(2-\sigma)\operatorname{opt}_k@@。
恢复轨道从真实锚点出发，比较解只在分析里用来识别”有利随机历史”。状态由 @@M@@S@@ 的幸存成员与挂在被采样客户上的叶子哑元（leaf dummy）组成；每步按客户到参考集的距离成比例采样，再在其周围猜一个球（ball），或移除其当前服务的原设施。半径菜单由总体半径控制，大菜单下标只出现在互不相交的客户集上，其比较费用恰好支付半径，故不利历史的总概率为 @@M@@\exp(-O(m))@@——这正是单指数依赖的来源，使 @@M@@m=O(\log N)@@ 时仍多项式可行。算法保存每一步前缀，无需知道比较划分即可停在有用状态。补全阶段：落在无球覆盖的坏中心处的移除目的地由精确子集动态规划优化；其余目的地用”每球取一设施、最大化单调次模节省（monotone submodular saving）”决定，分区约束的类别连续贪心给出 @@M@@1-1/e@@ 期望增益，把超支 @@M@@2P@@ 中的 @@M@@1-1/e@@ 比例省下、只剩 @@M@@2P/e@@，合计恰为 @@M@@1+2/e@@。构造每移除 @@M@@m@@ 个原设施至多新增 @@M@@m@@ 个，预算严格成立；精化一节再用两次相继的停时规则把估计收紧到 @@M@@1+2/e+\varepsilon@@。
支付轨道固定剩余构造的最终价格 @@M@@\lambda@@ 与副本长度，只重放其最终有效序列：一个客户预算势支付常规开设，相位的精确极大性给出”不超额叫价”不等式；证明把客户移除排序并取后缀最大值，两个互补松弛（complementary slackness）估计表明所有预算不等式同时近等式会强制早、晚期行为不相容，从而得到与客户数无关的有界价格缺口。
最后合并，令 @@M@@L=O(\log N)@@：若把预算从 @@M@@k@@ 降到 @@M@@k-2L@@ 最优几乎不变，则在目标 @@M@@k-L@@ 上运行剩余构造，剩余腾出空间、严格性把费用压到 2 以下；否则由乘积论证存在对删中心敏感的基数 @@M@@h'@@，其最优解满足簇分离 @@M@@n_i\operatorname{sep}_i\ge\beta P@@，锚定后只留 @@M@@O(L)@@ 个坏簇，恢复算法给出 @@M@@1.97(1+\xi)@@。算法把两种情形的候选都算出并取最便宜者，全程不测试任何最优值；再用度量舍入引理把整数度量结论转移回一般有理度量，常量选取使 @@M@@(2-\gamma)(1+\gamma/16)^2\le2-\gamma/2@@，期望再吸收失败事件即得 @@M@@2-\sigma@@。
本文主结果已 Lean 形式化，是族 125 中验证状态最好的一篇。姊妹篇《The approximation threshold for metric k-median》在同一候选设施模型上给出确定性的 @@M@@(1+2/e+\varepsilon)@@ 近似，其图舍入证明与本文的恢复/支付证明相互独立，两篇合并构成族 125 的完整图景：确定性阈值 @@M@@1+2/e@@，随机可到 @@M@@2@@ 以下。按 OpenAI 官方声明，未经形式化的结果可能有问题；本文虽已形式化，但全局应用把 CGLSS 的对数剩余构造当作外部输入，该外部部分仍请以原文与社区核验为准。
问 1：恢复证明中最关键、也最脆弱的一步在哪里？
答：不利历史概率的摊销。采样步按距离比例选客户、猜球或移除原设施，半径菜单由总体半径控制；证明要求”大菜单下标只出现在互不相交的客户集上，其比较费用恰好支付半径”，从而总概率损失为 exp(−O(m))。这条尺度假设是单指数依赖的全部来源——若某些大半径事件可以重叠计费，指数立即放大，m=O(log N) 时多项式可行性即告失守。
问 2：为什么必须假设”存在比较解与代理承诺”，却在归一化度量上工作？
答：算法拿不到比较解 O、分簇与代理，它们只在分析中标识”有利随机历史”——没有此承诺，锚点可能整体偏差而无从修补。归一化（正整数距离、多项式有界直径）同样必要：论文明确指出原始度量的代理在截断舍入后不一定保持精度，故锚点须在归一化之后构造，再由单独的转移论证把费用界搬回原度量。
问 3：相对 CGLSS（2+ε）与 FPT 工作，真正新意是什么？
答：CGLSS 的架构被保留（对数剩余＋删中心敏感实例的恢复），但恢复侧的例外簇依赖被压到单指数——引言明确指出 FPT 结果的 k^{O(k)} 依赖在 k=O(log N) 时不会自动变多项式，本文定理区分的正是”对坏簇数的依赖”。支付侧给出一次相容执行的自含有界价格证明（作者也承认 CGLS 附录 B 的数值缺口更强）。合成后首次做到严格小于 2 且每个输出不超过 k 家设施。
问 4：AI 生成证明最可能在哪里出错？
答：接口相容性。本文主结果已 Lean 形式化，但全局应用把 CGLSS 的有效序列合并构造当作外部输入使用——固定其最终价格与副本长度后只重放最终序列，三种结论必须引用同一预算向量。形式化覆盖的是本文定理的陈述，外部构造与接口假设的匹配是残留风险点；”常规/免费开设分开处理”的终对偶论证也依赖这一相容性。
问 5：σ 到底多大，1+2/e 从哪来？
答：论文只断言绝对常数 σ>0，未给显式数值；恢复的中间保证 1+2/e 来自分区约束的类别连续贪心（1−1/e 增益）省下超支 2P 的 1−1/e、余 2P/e，两次相继停时规则再把估计收紧到 1+2/e+ε，组合后可得 1.97(1+ξ) 一类的中间值。
问 6：高概率与期望同时成立是怎么做到的，谁会用它？
| 答：失败事件由度量舍入引理与有界费用的局部搜索回退吸收，故同一算法既给 ( | D | + | F | +2)^{-a} 的尾界也给期望界。受众是设施选址与聚类近似算法社区——它打破了”严格小于 2 必须放宽设施数预算”的长期障碍，与姊妹篇的确定性 1+2/e+ε 合成族 125 的完整图景。 |
总评
这是把 k-中值近似比推到 2 以下、且分文不超预算的第一份完整分析，恢复与支付双工具的合成干净有力；虽有 Lean 形式化加持，最大残留风险在对外部 CGLSS 构造的接口依赖与 σ 的非显式性。