悬挂数十年的 k-server 猜想获完整证明

Christian Coester、Elias Koutsoupias 与 Marek Zbysiński 在 arXiv 发布论文《The k-server conjecture is true》，给出在线算法领域经典难题 k-server 猜想的完整证明：确定性在线算法在每个度量空间上都能达到竞争比 k。这是理论计算机科学界近期「开放问题被攻克」集中爆发的一部分，多个悬置多年的公开问题接连告破。

2026-09-15 ~ 2026-09-16 · 3 条相关

• k-server 猜想被证明,在线算法理论再下一城 — minilek · 2026-09-15
• 悬挂数十年的 k-server 猜想被证明，arXiv 论文给出完整证明 — ctjlewis · 2026-09-16

另有 1 条近重复转述:naval