The Design and Analysis of a Modified Work Function Algorithm for Solving the On-Line k-Server Problem

Authors

  • Alfonzo Baumgartner
  • Tomislav Rudec
  • Robert Manger

Keywords:

On-line problems, on-line algorithms, k-server problem, fork function algorithm (WFA), moving windows, competitiveness, implementation, network flows, experiments, performance, computational complexity

Abstract

In this paper we study a modified work function algorithm (WFA) for solving the on-line k-server problem. Our modification is based on a moving window, i.e. on an approximate work function that takes into account only a fixed number of most recent on-line requests. We give a precise specification of the modified WFA, investigate its competitiveness, and explain how it can be implemented efficiently by network flows. We also present experiments that measure the performance and computational complexity of the implemented algorithm. The results of the paper can be summarized as follows: the modified WFA is not competitive, but according to the experiments it still provides almost the same quality of serving as the original WFA while running much faster.

Downloads

Download data is not yet available.

Author Biographies

Alfonzo Baumgartner

Faculty of Electrical Engineering, University of Osijek
Kneza Trpimira 2b, 31000 Osijek, Croatia

Tomislav Rudec

Faculty of Electrical Engineering, University of Osijek
Kneza Trpimira 2b, 31000 Osijek, Croatia

Robert Manger

Department of Mathematics, University of Zagreb
Bijenička cesta 30, 10000 Zagreb, Croatia

Downloads

Published

2012-01-26

How to Cite

Baumgartner, A., Rudec, T., & Manger, R. (2012). The Design and Analysis of a Modified Work Function Algorithm for Solving the On-Line k-Server Problem. Computing and Informatics, 29(4), 681–700. Retrieved from http://147.213.75.17/ojs/index.php/cai/article/view/108