k-median 近似比首次突破 2:1.95-LMP 新算法登上 arXiv
thomasahle · x · 2026-10-16
AlgoSvensson 团队宣布其 k-median 更优于 2 的近似结果正式上 arXiv(2610.18144)。背景颇具戏剧性:OpenAI 近期解决了这个团队学生耕耘一年多的同一问题,作者们在「遗憾」之余发布了自家的不同算法路线。
论文核心:
- Jain 等人的经典 Greedy 算法作为设施选址的 LMP(Lagrangian 乘子保持)近似算法,其 2-LMP 保证统治 k-median 二十余年,近期才被局部搜索后处理以极小幅度(η≈2.25×10⁻⁷)打破。
- 本文改换思路:不依赖最坏实例结构,而是改造算法本身——用一般化竞价函数(general bidding)替代经典线性竞价,证明多项式时间 1.95-LMP 近似,大幅改进长期保持的因子 2。
- 进一步证明这些广义竞价规则可做到平滑(log-adaptive),结合配套论文中稳定实例的 (1.89+ε) 近似,可开启 k+Oε(log n) 个中心。
作者特别致谢 Toni Jubés Monforte——他两年前硕士论文的work奠定了因子揭示 LP 分析的基础。
「研究」频道最新
- NVIDIA NVFP4 新压缩技巧:利用行内尺度相近性省 45-48% 存储且位精确 — TheZachMueller · 2026-10-16
- Goodfire Cammarata 长文:神经网络本就干净,可解释性前景远超预期 — BorisMPower · 2026-10-16
- 拿 Jev 等「决策模型」跑电车难题:它选择不拉杆以保住自己的服务器 — dbreunig · 2026-10-16
- OpenAI 推出 Rosalind Academic 计划,美国高校实验室可获赞助使用 — OpenAI · 2026-10-16
- 从激活图谱到今日特征可视化:神经元可解释性肉眼可见地跃升 — MajmudarAdam · 2026-10-16
- 可解释性研究者激辩：模型可达 99% 可解释的说法靠不靠谱 — livgorton · 2026-10-16