Deterministic 3-Server on a Circle and the Limitation of Canonical Potentials

Zhiyi Huang, Hanwen Zhang

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 functi…