k-server猜想成立

计算机科学 > 数据结构和算法 arXiv:2609.15979 (cs) [提交于 2026 年 9 月 14 日] 标题：$k$-服务器猜想为真 作者：Christian Coester、Elias Koutsoupias、Marek Zbysiński 查看标题为“$k$-服务器猜想为真”的论文的 PDF，作者为 Christian Coester 和其他 2 位作者 查看 PDF HTML （实验）摘要：$k$-服务器猜想指出，确定性在线算法可以在每个度量空间上实现竞争比 $k$。我们证明猜想。具体来说，我们证明工作函数算法满足它。我们的证明使用功函数的自然代数表示作为矩阵，它对所有可行路径进行编码以达到配置。在这种表示中，最优成本定义中出现的最小和加法运算对应于形式表达式的加法和乘法，并且每个功函数值对应于矩阵的$k$列的行列式。请求到达通过更改基础和行替换来更新表示。摊销分析基于根据较大矩阵定义的势函数，该矩阵的坐标是原始矩阵表示的坐标对。主题：数据结构和算法 (cs.DS) 引用为：arXiv:2609.15979 [cs.DS]（或此版本的 arXiv:2609.15979v1 [cs.DS]） https://doi.org/10.48550/arXiv.2609.15979 arXiv 通过 DataCite 发布的 DOI（待定）提交历史记录 发件人：Marek Zbysiński [ 查看电子邮件 ] [v1] 2026 年 9 月 14 日星期一 17:58:11 UTC (22 KB) 全文链接： 访问论文：查看 Christian Coester 和其他 2 位作者撰写的题为 The $k$-server conjecture is true 的论文 PDF 查看 PDF HTML（实验性） TeX 源代码 查看许可证 当前浏览上下文：cs.DS < prev | 注册）下一页 > 新 |最近 | 2026-09 更改浏览方式： cs 参考文献和引文 NASA ADS Google Scholar 语义学者正在加载... BibTeX 格式的引文正在加载... 数据提供者： 书签 书目工具 书目和引文工具 书目浏览器切换 书目浏览器（什么是浏览器？） 关联论文 切换 关联论文（ 什么是关联论文？） Litmaps 切换Litmaps（什么是 Litmaps？） scite.ai 切换 scite 智能引文（什么是智能引文？） 与本文相关的代码、数据、媒体代码、数据和媒体 alphaXiv 切换 alphaXiv（什么是 alphaXiv？） 代码链接 切换 CatalyzeX 论文代码查找器（什么是 CatalyzeX？） DagsHub 切换 DagsHub（什么是DagsHub？）GotitPub 切换 Gotit.pub（什么是 GotitPub？）Huggingface 切换拥抱脸（什么是 Huggingface？）ScienceCast 切换 ScienceCast（什么是 ScienceCast？）演示演示复制切换复制（什么是复制？）空间切换拥抱脸空间（什么是空间？）空间切换 TXYZ.AI（什么）是 TXYZ.AI？） 相关论文推荐器和搜索工具 影响花链接 影响花（什么是影响花？） 核心推荐器切换 核心推荐器（什么是 CORE？） 作者地点 机构 主题 关于 arXivLabs arXivLabs：与社区合作者的实验项目 arXivLabs 是一个框架，允许合作者直接在我们的网站上开发和共享新的 arXiv 功能。与 arXivLabs 合作的个人和组织都接受并接受了我们开放、社区、卓越和用户数据隐私的价值观。 arXiv 致力于这些价值观，并且只与遵守这些价值观的合作伙伴合作。您有一个能为 arXiv 社区增加价值的项目想法吗？了解有关 arXivLabs 的更多信息。这篇论文的哪些作者是认可者？ |禁用MathJax（什么是MathJax？）