engleski

On the Competitiveness of a Modified Work Function Algorithm for Solving the On-Line k-Server Problem

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.

on-line problems; on-line algorithms; k-server problem; work function algorithm (WFA); moving windows; competitiveness

nije evidentirano