On the Additive Constant of the k-server Work Function Algorithm

Yuval Emek, Pierre Fraigniaud, Amos Korman +1

We consider the Work Function Algorithm for the k-server problem. We show that if the Work Function Algorithm is c-competitive, then it is also strictly (2c)-competitive. As a cons…