On the Competitiveness of a Modified Work Function Algorithm for Solving the On-Line k-Server Problem (CROSBI ID 545309)
Prilog sa skupa u zborniku | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Rudec, Tomislav ; Manger, Robert
engleski
On the Competitiveness of a Modified Work Function Algorithm for Solving the On-Line k-Server Problem
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.
on-line problems; on-line algorithms; k-server problem; work function algorithm (WFA); moving windows; competitiveness
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o prilogu
779-784.
2008.
objavljeno
Podaci o matičnoj publikaciji
Proceedings of the 30th International Conference on Information Technology Interfaces (ITI 2008 - Cavtat, Croatia, June 23-26, 2008)
Lužar-Stiffler, Vesna ; Dobrić Hljuz, Vesna ; Bekić, Zoran
Zagreb: Sveučilišni računski centar Sveučilišta u Zagrebu (Srce)
Podaci o skupu
International Conference on Information Technology Interfaces (ITI 2008)
predavanje
23.06.2008-26.06.2008
Cavtat, Hrvatska