Izvorni znanstveni članak
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
Sažetak
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.
Ključne riječi
k-server problem; off-line algorithms; on-line algorithms; optimality; implementation; network flows; execution time; experiments
Hrčak ID:
37440
URI
Datum izdavanja:
3.6.2009.
Posjeta: 1.794 *