k-server 猜想被证明,在线算法理论再下一城
minilek · x · 2026-09-15
理论计算机科学界迎来一波「开放问题被攻克」的集中爆发。Aaroth 在推文中列举了当天被解决的几个经典开放问题:
- k-server 猜想:Christian Coester、Elias Koutsoupias、Marek Zbysiński 提交论文《The k-server conjecture is true》,证明确定性在线算法在每个度量空间上都能达到竞争比 k,具体证明工作函数算法(work function algorithm)满足该界。
- Matroid Secretary 问题
- Matrix Spencer 问题(可能几周前已被解决)
证明思路:把工作函数表示为矩阵,用代数形式编码所有可行路径,最优代价中的 min/加法运算对应形式表达式的加法与乘法,每个工作函数值对应矩阵 k 列的行列式;请求到达时通过基变换与行替换更新表示,摊还分析基于一个更大矩阵上的势函数。
Aaroth 同时给出判断:我们正走向一个「没有开放问题」的世界,但这不意味着数学消失——有意思的工作将转向发现新问题和构建自洽的理论框架,定义清晰、公认有趣的问题不会存活太久。
所属事件:k-server 猜想被证明，在线算法理论迎来突破(2 条相关)→
「研究」频道最新
- GenSyn 发布 OPEN-1B：训练过程可逐位重放验证的 1B 开源模型 — benfielding · 2026-09-15
- Anthropic 论文:双下降是记忆样本到学习结构的相变 — gordic_aleksa · 2026-09-15
- 机制可解释性研究：双重下降是记忆与泛化的相变 — gordic_aleksa · 2026-09-15
- 新论文把权威资料转成考题，系统评测 LLM 职业知识 — RishiBommasani · 2026-09-15
- TabPFN-3.5 发布：支持时序与分组数据，推理最快提速 6 倍 — FrankRHutter · 2026-09-15
- Google 发报告:1500 万次 Gemini 交互揭示 AI 如何改变科学研究 — danielrock · 2026-09-15