Skip to the main content

Mathematical Communications, Vol. 14 No. 1, 2009.

Original scientific paper

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

Tomislav Rudec ; Faculty of Electrical Engineering, University of Osijek, Osijek, Croatia
Alfonzo Baumgartner ; Faculty of Electrical Engineering, University of Osijek, Osijek, Croatia
Robert Manger ; Department of Mathematics, University of Zagreb, Zagreb, Croatia

Full text: english pdf 374 Kb

page 119-134

downloads: 1.354

cite

Abstract

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.

Keywords

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

Hrčak ID:

37440

URI

https://hrcak.srce.hr/37440

Publication date:

3.6.2009.

Visits: 1.794 *