engleski

A fast implementation of the optimal off-line algorithm for solving the k-server problem

The optimal off-line algorithm for solving the k-server problem is usually implemented by network flows. In this paper, we first propose certain modifications to each step of the original network-flow implementation. Next, by experiments we demonstrate that the proposed modifications improve the speed of the algorithm. Finally, we investigate how similar ideas for improvement can also be applied to some related on-line algorithms.

k-server problem; off-line algorithms; on-line algorithms; optimality; implementation; network flows; execution time; experiments

nije evidentirano