@@M@@k@@-median结果族 125：The metric
@@M@@k@@-median approximation threshold and recovery · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
还是开连锁店选址,这次追求”确定性”与”精确极限”:论文给出一个不掷骰子的多项式时间算法,总路程不超过最优的 @@M@@1+2/e+\varepsilon\approx1.74@@ 倍;同时证明除非 @@M@@P=NP@@,任何快速算法都不可能稳定做到 @@M@@1+2/e@@ 以下。能到达的天花板与不可逾越的地板,被焊死在同一点上。
关键词卡片
@@M@@k@@-中值(metric k-median):从候选地址选至多 @@M@@k@@ 家门店,最小化顾客总路程。@@M@@1+2/e@@。看个具体例子
硬度来自 Max-@@M@@k@@-Coverage 的归约:元素当顾客、集合当候选地址,同类点距离 2、关联对 1、无关对 3。
公式卡 选 @@M@@k@@ 个集合覆盖 @@M@@c@@ 个元素 @@M@@\Leftrightarrow@@ 总路程 @@M@@=3m-2c@@;完美覆盖时路程为 @@M@@m@@,而覆盖比例至多 @@M@@1-1/e+\delta@@,两者之比 @@M@@=\dfrac{3m-2(1-1/e+\delta)m}{m}=1+2/e-2\delta\approx1.736@@。
算法侧,论文的”锥形迭代舍入”在输入编码长度的多项式时间内(次数可依赖 @@M@@\varepsilon@@)恰好做到 @@M@@1+2/e+\varepsilon@@,且至多开 @@M@@k@@ 家门店;两边合拢,阈值被精确钉死在 @@M@@1+2/e\approx1.7358@@。
为什么值得关心
近似比从 1994 年的 3 一路缓降至 2025 年的 @@M@@2+\varepsilon@@,与硬度 @@M@@1.736@@ 之间的空隙悬置多年;本文把它填平,带候选设施的度量 @@M@@k@@-中值近似比问题在 @@M@@P\ne NP@@ 下正式结案。
暂无形式化证明(AI 结果待核验)
第一级台阶
还是导读里那条”开连锁店”的街：对象是客户位置与候选店址，操作仍是挑至多 k 家店、让顾客总路程最短。但这回有两点不同：算法不掷骰子——同样的输入永远给出同样的输出；而且要追求”精确极限”——能到达的天花板与不可逾越的地板被焊死在同一个数字上。
第二级台阶
用本科术语装备三件工具。指派线性规划：开设变量 y_i 允许取小数（相当于”开半家店”），总开设质量至多 k、费用至多最优值；网格化：把小数开设量吸附成 1/Δ 的整数倍，便于按”副本”操作；锥形迭代舍入：每轮由一张有向图规定，当某个源副本的设施开设时擦除哪些目标副本，擦除概率随距离线性锥形递减。近似阈值指多项式时间可保证因子的下确界。
第三级台阶
主定理在这样的语境下陈述：对每个固定的 ε>0，存在确定性算法在输入编码长度的多项式时间内返回至多 k 个设施，费用不超过 (1+2/e+ε)·OPT。假设各有分工：候选设施集作为输入显式给出——硬度归约需要一个与客户集不相交的设施集，F=J 的模型是另一个问题；距离为二进制有理数，保证多项式位复杂度有意义。另一侧是来自 Max-k-Coverage 的归约（完美覆盖与至多覆盖 1−1/e+δ 比例之间的缺口）：只要 P≠NP，任何多项式算法都不能稳定做到 1+2/e 以下。两股力量合拢，结论用上面的术语说：该模型多项式时间近似因子的下确界恰为 1+2/e——注意是下确界，定理不声称达到端点本身。
本文对带指定候选设施的有限有理度量 @@M@@k@@-中值给出任意固定 @@M@@\varepsilon>0@@ 的确定性多项式时间 @@M@@(1+2/e+\varepsilon)@@-近似算法；结合 Max-@@M@@k@@-Coverage 的 @@M@@1+2/e@@ 硬度，在 @@M@@P\ne NP@@ 下该模型多项式时间近似的下确界因子恰为 @@M@@1+2/e@@，近似阈值被完全确定。
度量 @@M@@k@@-中值（metric @@M@@k@@-median）给定客户集 @@M@@J@@、候选设施集 @@M@@F@@ 与整数 @@M@@k@@，要求选至多 @@M@@k@@ 个设施最小化连接费用 @@M@@\sum_{j\in J}d(j,S)@@。三十年主线包括 LP 舍入（Charikar–Guha–Tardos–Shmoys，首个常数因子）、Lagrange 松弛与原始-对偶（Jain–Vazirani）、对偶拟合（Jain 等）以及交换局部搜索（Arya 等，@@M@@3+\varepsilon@@）；Li–Svensson 用”常数加性伪近似可转为真近似”的约化打开缺口，bi-point 舍入推进到 2.675 与 2.613，2025 年起 CGLSS 与 Byrka 等人的迭代图舍入双双达到 @@M@@2+\varepsilon@@。下界方面，由 Feige 的覆盖缺口可继承 @@M@@1+2/e@@ 的不可近似性。悬而未决的问题是：@@M@@2+\varepsilon@@ 与 @@M@@1+2/e@@ 之间的大片空隙能否填满？本文给出肯定回答，而且算法是确定性的。
主定理：对每个固定 @@M@@\varepsilon>0@@，存在确定性算法，在输入二元编码长度的多项式时间（次数可依赖 @@M@@\varepsilon@@）内返回 @@M@@S\subseteq F@@、@@M@@|S|\le k@@，使得 @@M@@\sum_{j\in J}d(j,S)\le(1+2/e+\varepsilon)\operatorname{OPT}_k@@。推论：若 @@M@@P\ne NP@@，该模型确定性多项式时间近似因子的下确界（infimum）恰为 @@M@@1+2/e@@。硬度来自 Max-@@M@@k@@-Coverage：把宇宙元素作客户、集合作设施，同类点距离取 2、关联对取 1、非关联取 3，则所选 @@M@@k@@ 个集合覆盖 @@M@@c@@ 个元素当且仅当连接费用为 @@M@@3m-2c@@；完美覆盖的费用是 @@M@@m@@，而完美完备情形下至多覆盖 @@M@@1-1/e+\delta@@ 比例，于是任何多项式算法都被挡在 @@M@@1+2/e-2\delta@@ 之外。
证明分三段。第一段网格准备：先解标准指派 LP（开设变量 @@M@@y_i@@ 总质量至多 @@M@@k@@、费用至多 @@M@@\operatorname{OPT}_k@@），把开设量吸附为 @@M@@g=1/\Delta@@ 的整数倍（偶数 @@M@@\Delta@@ 只依赖精度），总质量至多增加 @@M@@3g@@，每个客户的期望指派费用近无损；再以分离的代表客户定义互不相交的”捆”（bundle），把每捆的亏缺（deficit）与其供应者（supplier）一并做依赖舍入（dependent rounding），既控制开设预算又控制恢复整单位指派的费用，并允许一个供应者服务多个客户——因为指派质量不是共享容量。第二段锥形迭代舍入是心脏：把每个正网格开设视为若干质量 @@M@@g@@ 的副本，每轮由有向图规定”源副本开设时擦除哪些目标副本”，每个目标恰有 @@M@@\Delta@@ 个入源，入边概率随距离线性锥形递减；开设与擦除按质量配平，只需常数个额外设施，擦除量过大的”重源”直接强制开设。费用分析对每个客户追踪其初始指派单位中幸存的副本与一个持续的距离上界，构造系数随时间衰减（参数 @@M@@x=e^{-\xi}@@）与幸存质量变化的势函数；当客户自己的副本开设时，继续追踪更便宜的幸存者，由此产生的减项恰好支付其他擦除。核心工具是一个有限比较不等式（finite comparison inequality），其解析函数 @@M@@A(x)=1+2\int_0^1(1-e^{-tx})\,dt@@、@@M@@P(x)=\int_0^1te^{-tx}\,dt@@、@@M@@m(x)=A-1-2xP@@ 满足 @@M@@A(1)=1+2/e@@——阈值常数正是从这条指数时间表自然涌现。该不等式处理一个未必对称的比较矩阵：正行的贡献只允许向 @@M@@D@@ 值更小的列”转账”，数值上正行满足 @@M@@D>0.4@@ 而收款行满足 @@M@@D<0.394@@，两类严格分离，接收行的负贡献逐行覆盖全部进账。重源的强制开设依赖实现图，证明先对每个实现图界定势变化、再对图取平均，避免对图依赖事件做条件化。舍入定理最终给出每个客户 @@M@@\E d(j,O)\le(1+2/e+\tau)V_{j,0}@@ 且 @@M@@|O|\le M+C@@。第三段去随机化并回收预算：所有界只依赖各局部选择的指定低阶矩，故可构造保持这些矩的多项式规模有理分布（Carathéodory 型支撑缩减），对常数轮展开全部物理历史并取满足加性预算的最便宜输出，得到开至多 @@M@@k+c@@ 设施的确定性近似；最后用 Li–Svensson 约化以任意小的附加损失去掉常数剩余 @@M@@c@@。
本文暂无形式化证明，请以社区核验为准；论文把关键标量不等式的每条估计都配了显式的有理多项式证书（附录），这部分可机器复核。姊妹篇《Single-exponential recovery and bounded-price strictness》在同一模型上独立给出随机的 @@M@@(2-\sigma)@@-近似且主结果已 Lean 形式化，两篇证明路线独立、互为印证。按 OpenAI 官方声明，未经形式化的结果可能有问题，本文的去随机化与有理算术细节尤待同行仔细核验。
问 1：证明中最关键、也最脆弱的一步在哪里？
答：有限比较不等式（inequality 节）。锥形迭代舍入的费用分析最终折算成一个有限维、未必对称的比较矩阵不等式：正行的贡献只允许向 D 值更小的列”转账”（数值上正行 D>0.4、收款行 D<0.394，两类严格分离），阈值常数由解析函数 A(x)=1+2∫₀¹(1−e^{−tx})dt 在 x=1 处的值 1+2/e 涌现。这一步若失效，整个因子就退回 2；好在论文为每条标量估计配了显式有理多项式证书（附录），这部分可机器复核。
问 2：为什么限定”指定候选设施”模型？F=J 会怎样？
答：硬度方向由 Max-k-Coverage 归约给出，需要元素作客户、集合作不相交的设施集，再显式补全成度量；若强制 F=J，该归约无处落脚，论文明确引用 Anand–Lee 指出那是不同的问题。算法侧对 F=J 并无障碍，但阈值结案只在候选设施模型内成立。
问 3：相对 Byrka 等（2026）的迭代图舍入框架，真正新意是什么？
答：源开设—邻擦除的物理框架、平衡批与强制开设承自该文第 3–6 节，但其一般转移定理在 k-中值情形的参数至少为 2，给不出更小因子。本文换掉了费用分析：引入保留幸存指派的势函数（系数随时间以 x=e^{−ξ} 衰减），客户自己的副本开设后继续追踪更便宜的幸存者，产生的减项恰好支付其他擦除——这才把因子压到 1+2/e+ε。
问 4：AI 生成证明最可能在哪里出错？
答：两处。其一，”重源强制开设”依赖实现图：证明必须先对每个实现图界定势变化、再对图取平均，一旦顺序颠倒对图依赖事件做了条件化，漂移界即失效——这类顺序错误机器极难自查。其二，去随机化声称”所有界只依赖各局部选择的指定低阶矩”，若某个矩实际影响了某步而未被保持，确定性保证悄然落空；有理编码界的多项式性论证同样冗长易碎。
问 5：先开 k+c 家再用 Li–Svensson 约化去掉剩余，为何合法？
答：Li–Svensson 的约化正是为”常数加性伪近似转真近似”设计的前置工具：常数量额外设施可用任意小的附加近似损失移除。本文只做调用，代价是因子里那点 ε 的来源。
问 6：这个阈值结果谁会用？
答：聚类与设施选址的近似算法社区——k-中值在候选设施模型下的近似比问题就此结案，三十年的因子序列（3、2.675、2.613、2+ε）画上句号。与姊妹篇的随机 (2−σ) 结果路线独立、互为印证；F=J 模型的对应阈值与更强硬度假设下的结论，论文未展开。
总评
把上限压到与 Feige 覆盖缺口相同的 1+2/e+ε 并显式去随机化，分量是”结案级”的；最大风险在未经形式化的势函数—比较不等式链条与去随机化的矩清单，任何一处漏项都会让因子悄悄退回 2。