Naslov
On the Competitiveness of a Modified Work Function Algorithm for Solving the On-Line k-Server Problem

Autori
Rudec, Tomislav ; Manger, Robert

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Izvornik
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), 2008, 779-784

Skup
International Conference on Information Technology Interfaces (ITI 2008)

Mjesto i datum
Cavtat, Hrvatska, 23.06.2008. - 26.06.2008

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
on-line problems; on-line algorithms; k-server problem; work function algorithm (WFA); moving windows; competitiveness

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA