On the competitiveness of a modified work function algorithm for solving the on-line k-server problem
Tomislav Rudec, Robert Manger · 2008
We study a modification of the well known work function algorithm (WFA) for solving the on-line k-server problem. Our modified WFA is based on a moving window, i.e. on the approximate work function that takes into account only a fixed number of most recent on-line requests. In this paper we prove that, in contrast to the original WFA, the modified WFA is not competitive. Our proof is based on a suitably constructed problem instance showing that the performance of the modified WFA can be an arbitrary number of times worse than optimal.