Title :
On the competitiveness of a modified work function algorithm for solving the on-line k-server problem
Author :
Rudec, Tomislav ; Manger, Robert
Author_Institution :
Fac. of Electr. Eng., Osijek Univ., Osijek
Abstract :
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 prove that, in contrast to the original WFA, the modified WFA is not competitive. Our proof is based on a suitably constructed problem instance showing that the performance of the modified WFA can be an arbitrary number of times worse than optimal.
Keywords :
algorithm theory; queueing theory; modified work function algorithm; moving window; on-line k-server problem; Computational complexity; Cost function; Degradation; Extraterrestrial measurements; Information technology; Lighting control; Mathematics; Size control; competitiveness; k-server problem; moving windows; on-line algorithms; on-line problems; work function algorithm (WFA);
Conference_Titel :
Information Technology Interfaces, 2008. ITI 2008. 30th International Conference on
Conference_Location :
Dubrovnik
Print_ISBN :
978-953-7138-12-7
Electronic_ISBN :
1330-1012
DOI :
10.1109/ITI.2008.4588510