The $k$-server conjecture is true

Christian Coester, Elias Koutsoupias, Marek Zbysiński

The $k$-server conjecture states that a deterministic online algorithm can achieve competitive ratio $k$ on every metric space. We prove the conjecture. Specifically, we show that…