论文标题
确定性的3服务器在一个圆圈和规范势的限制
Deterministic 3-Server on a Circle and the Limitation of Canonical Potentials
论文作者
论文摘要
确定性的$ k $ -server猜想指出，对于任何公制空间，$ k $ server问题都有$ k $竞争性的确定性算法。我们证明，对于圆圈指标上的$ 3 $ - 服务器问题的工作功能算法是$ 3 $竞争的，Coester和Koutsoupias（2021）留下了一个案例。我们的分析遵循现有的框架，但引入了新的潜在功能，该功能可能被认为是Coester和Koutsoupias（2021）对同行的放松。我们进一步注意到，新的潜在功能和许多现有功能可以以规范的形式重写。但是，通过计算机辅助验证，我们发现没有这样的规范潜在功能可以解决当前分析框架下的一般度量空间的确定性$ 3 $ - 服务器的猜想。
The deterministic $k$-server conjecture states that there is a $k$-competitive deterministic algorithm for the $k$-server problem for any metric space. We show that the work function algorithm is $3$-competitive for the $3$-server problem on circle metrics, a case left open by Coester and Koutsoupias (2021). Our analysis follows the existing framework but introduces a new potential function which may be viewed as a relaxation of the counterpart by Coester and Koutsoupias (2021). We further notice that the new potential function and many existing ones can be rewritten in a canonical form. Through a computer-aided verification, however, we find that no such canonical potential function can resolve the deterministic $3$-server conjecture for general metric spaces under the current analysis framework.
