engleski

A network flow implementation of a modified work function algorithm for solving the 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 describe in detail a network flow implementation of the modified WFA. We also present theoretical estimates and experimental measurements dealing with the computational complexity of the implemented algorithm.

on-line problems; on-line algorithms; k-server problem; work function algorithm (WFA); moving windows; implementation; network flows; computational complexity

nije evidentirano