Naslov
Measuring True Performance of the Work Function Algorithm for Solving the On-Line k-Server Problem

Autori
Rudec, Tomislav ; Baumgartner, Alfonzo ; Manger, Robert

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

Izvornik
Proceedings of the ITI 2010 32nd International Conference on Information Technology Interfaces / Lužar-Stiffler, Vesna ; Jarec, Iva ; Bekić, Zoran - Zagreb : Sveučilišni računski centar Sveučilišta u Zagrebu (Srce), 2010, 695-700

ISBN
978-953-7138-18-9

Skup
32nd International Conference on Information Technology Interfaces - ITI 2010

Mjesto i datum
Cavtat, Hrvatska, 21.06.2010. - 24.06.2010

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); experiments.

Sažetak
This paper deals with the work function algorithm (WFA) for solving the on-line k-server problem. The paper is concerned with assessing actual performance of the WFA in terms of its serving costs. First, an efficient implementation of the WFA is briefly described. Next, some experiments are presented, where the performance of the implemented WFA has been measured on very large problem instances. Thereby, the problem instances have been selected from some frequently studied classes where sharp theoretical estimates of performance are available. Finally, the measured performance of the WFA is compared with the corresponding theoretical estimates and with some other algorithms.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA