A Better-than-2 Approximation for k-Median Part I: The Power of General Bids
Rares-Darius Buhai, Vincent Cohen-Addad, Henry Fleischmann, Anupam Gupta, Antoni Jubés Monforte, Madhusudhan Reddy Pittu, Miltiadis Stouras, Ola Svensson, Lukas Vogl
cs.DS
2026-10-13
把贪心出价从 [α−d]+ 改成 [α−1.224d]+ 后,设施选址的 LMP 比从 2 降到 1.9499;再接上对数自适应和稳定实例算法,度量 k-median 在多项式时间里做到 1.95 近似。
度量 k-median 是在三角不等式下选 k 个中心,让 n 个客户到最近中心的距离之和最小。已知硬度是 1+2/e,多项式算法有二十多年停在 2 附近。卡点是 Jain、Vazirani 的拉格朗日归约。
基数约束被写成均匀开设费 f。对 f 二分,得到开得少于 k 个和多于 k 个的两份设施选址解,凸组合在期望意义下开出 k 个中心。这一步要求 LMP 近似:开设费按原价付清之后,连接成本仍不超过最优总代价扣除开设费的 α 倍。经典贪心出价 [α−d]+ 的 LMP 比是 2,双点舍入再乘 2,k-median 只能到 4。
后来允许多开 O(1) 个中心。双点舍入改进后,叠上只比 2 小 η≈2.25×10^{-7} 的局部搜索后处理,近似比到 2.613。对数自适应贪心和标准 LP 的迭代舍入都收到 2+ε。期望开 k 个和硬性至多开 k 个,两边顶在 2。普通设施选址已有 1.488 近似,但不保证 LMP,接不进这套归约。
贪心的流程不变。活跃客户共用一个上涨的预算 α,出价凑满开设费就开中心,预算够付到已开中心的距离就停止。变的是出价。经典规则把 α 减去距离后的剩余全部投出。这篇用 β(α,d)=[α−γd]+,γ=1.224。距离先乘 γ 再扣,远中心收到的钱更少。
出价要合法:不能超过剩余预算,还要单调、可按比例缩放,并且超可加。超可加管的是记账。客户的真实花费是第一次被服务时的出价,加上后来每次改连更近中心的出价,再加最终连接距离。线性出价下这些项抵消,花费等于冻结的 α。γ>1 之后抵消失败。继续用 α 上界花费的话,论文图 3 的比值会回到 2。
旧的紧例把 n−1 个客户放在贵的中心上,另一个客户到两个相距 2 的中心距离都是 1。线性出价会先开便宜中心,比值趋于 2。γ>1 时便宜中心拿不够钱,比值降到不超过 γ。改到对每个 γ∈(1, 1.224] 都紧之后,比值是 2−(1−γ)^2−1/n。γ=1.224 时这个数不超过 1.9499。
定理 4.4 证明,γ∈[1, 1.224] 时 factor-revealing 程序对所有 n 不超过 2−(γ−1)^2,和这个构造对齐。开设费按 1.9499 倍代入贪心,得到真正开设费下的 1.9499-LMP。程序不是单个 LP:每一段出价是否为正要用 0-1 变量标出,形成 2^{Θ(n²)} 个线性规划。对偶解按客户第一次出正价的时刻适配,再用连续插值和中间值定理找到可行的建议变量。
双点舍入过不了 (1+2/e)√φ≈2.208,所以改走对数自适应。θ 按 1+ε² 增长,距离乘 1−δ。开第二类中心时,只有距中心 εθ 以内的客户可以把预算抬到当前 θ 以上。两种可开条件用了不同的距离缩放,因此同时成为候选的中心要么相距 ≤δθ,要么 ≥θ/γ。程序值 ≤ρ 且 ρ≥1.01γ 时,平滑版本是 (1+2δ)ρ-LMP。损失收进 ε 之后,定理 1.2 给出至多 k+O(log n/ε²) 个中心,代价 (1.9499+ε)·opt。
恰好 k 个中心还要伴生论文。最优值没被多开中心抬高多少时,伪解已经够用;否则出现 β-稳定规模,再少开一个中心,最优值至少涨 1+β。伴生论文以概率 1−ε 做到 (1.89+O(ε))·opt,ε 取在 1/200 以内。两半合成定理 1.1:随机多项式时间的 1.95 近似。
备注 1.5 用 13 段凸组合把 LMP 降到 1.844,系数是 Ws/10^8,斜率从 137/125 到 41/20,并证明任何合法出价的程序值至少 1.8。这两条是 GPT-6 Astra 的 Lean 证书。其余证明论文声明由作者独立完成。GPT-5.6 Sol 与 GPT-6 Astra 做了检查和改写,定理 4.4 的证书也来自 GPT-6 Astra。
| 方法 | 指标 | 结果 |
| 线性出价贪心 | LMP / k-median | 2 / 4 |
| 局部搜索后处理 | LMP | 2−η,η≈2.25×10^{-7} |
| 再加改进的双点舍入 | k-median | 2.613 |
| 对数自适应;LP 迭代舍入 | k-median | 2+ε |
| γ=1.224 | LMP | 1.9499 |
| 对数自适应版本 | 中心数与代价 | ≤k+O(log n/ε²),(1.9499+ε)·opt |
| 伴生论文,稳定实例 | 恰好 k 个中心 | (1.89+O(ε))·opt,概率 1−ε |
| 两篇合起来 | 多项式时间 k-median | 1.95 |
| 13 段混合出价 | LMP | 1.844 |
| 任意合法出价 | 程序下界 | 1.8 |
| 硬度 | k-median | 1+2/e |
| LMP 双点舍入 | 已知阈值 | (1+2/e)√φ≈2.208 |
1.9499 是 2−(1.224−1)^2 的上界。对 γ∈(1, 1.224],2−(1−γ)^2 被图 2 的构造打紧。
上一次 LMP 改进只有 2.25×10^{-7}。这篇在同一类贪心里把比值降到 1.9499,和 2 相差大约 0.05。2 绑在线性出价的紧例上。
平滑分析是黑箱。更好的合法出价可以沿用多开 O(log n/ε²) 个中心那一半,不用重写对数自适应的证明。1.844 就是沿这个方向走的一步,证据是 Lean 证书。
算法 1 只改了出价。1.95 的保证要穿过稳定实例子程序,时间里有 exp(O(1/β))。近似比往前走了,它不是一个更快的聚类器。
论文记录了同期的另外两条路。2026 年 10 月 6 日,OpenAI 宣布两个优于 2 的结果,其中一个把迭代舍入推到 1+2/e+ε。Byrka、Yuhao Guo、Yang Hu、Shi Li 等人也独立得到某个小常数 σ 的 2−σ。这些是宣布和私人通信。若 1+2/e+ε 成立,1.95 不会是最好的 k-median 常数。1.9499 的 LMP 仍是这篇出价分析自己的结论。
γ 只分析到 1.224,因为上界和紧例在这里重合,不是更广范围里搜出来的最优斜率。再增大 γ,论文没有上界。
1.8 是这套 factor-revealing 程序的下限。它和硬度 1+2/e 之间的空隙,换出价填不上。
1.95 跨两篇论文。这篇独立给出的是 1.9499-LMP,以及多开 O(log n/ε²) 个中心时的 (1.9499+ε)。恰好 k 个中心依赖伴生论文,稳定实例的证明这里核对不了。
对数自适应先付一个 (1+2δ),并要求 ρ≥1.01γ,δ 比 1/γ 足够小,ε 比 δ 足够小。任意小的 ε 能吸收这些损失,多项式次数会很高。没有实验,也没有具体 n 上额外中心个数的测量。
1.844 和 1.8 放在备注里,和手写的 1.9499 不是同一条证据链。同期的 1+2/e+ε 只有「宣布」,这篇没有收入对方证明。