悬挂数十年的 k-server 猜想被证明，arXiv 论文给出完整证明
ctjlewis · x · 2026-09-16
Christian Coester、Elias Koutsoupias 与 Marek Zbysiński 在 arXiv 发布论文，证明在线算法领域的经典难题 k-server 猜想成立：确定性在线算法可在任意度量空间上达到竞争比 k。证明思路是利用 work function algorithm，把 work function 表示为一个矩阵的代数结构——其中可行路径编码为形式表达式的加法与乘法，每个 work function 值对应矩阵 k 列的行列式；请求到达时通过换基与行替换更新表示，摊还分析则基于一个更大矩阵定义的势函数。
所属事件:悬挂数十年的 k-server 猜想获完整证明(3 条相关)→
「研究」频道最新
- Greg Brockman 官宣:OpenAI 在又一个千禧年数学难题上取得重大进展 — scaling01 · 2026-09-16
- OmegAMP 预印本:生成式 AI 可编程设计抗菌肽,204 条实验验证含体内疗效 — AllThingsApx · 2026-09-16
- 仅用 1300 块 H200,实验数据循环训练出超越 GPT-6 Astra 的材料模型 Neon — OriolVinyalsML · 2026-09-16
- Agent 基准新增真实故障任务:缓存令牌冒充用户 40 分钟 — Kind-Atmosphere9655 · 2026-09-16
- 千禧年大奖难题之争:OpenAI 疑与含 Anthropic 研究者的团队赛跑解 Navier-Stokes — thursdai_pod · 2026-09-16
- MICAFlow 论文发布：快速稳健的 MRI 预处理管线打通科研与临床 — bttyeo · 2026-09-16