Pretražite po imenu i prezimenu autora, mentora, urednika, prevoditelja

Napredna pretraga

Pregled bibliografske jedinice broj: 381173

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


Rudec, Tomislav; Manger, Robert
On the Competitiveness of a Modified Work Function Algorithm for Solving the On-Line k-Server Problem // 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 (ur.).
Zagreb: University Computing Centre, 2008. str. 779-784 (predavanje, međunarodna recenzija, cjeloviti rad (in extenso), znanstveni)


CROSBI ID: 381173 Za ispravke kontaktirajte CROSBI podršku putem web obrasca

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 : University Computing Centre, 2008, 779-784

Skup
International Conference on Information Technology Interfaces (ITI 2008)

Mjesto i datum
Cavtat, Hrvatska, 23-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


Projekt / tema
037-0362980-2774 - Distribuirani algoritmi za pronalaženje optimalnih putova u grafovima (Robert Manger, )

Ustanove
Prirodoslovno-matematički fakultet, Matematički odjel, Zagreb,
Fakultet elektrotehnike, računarstva i informacijskih tehnologija Osijek

Profili:

Avatar Url Tomislav Rudec (autor)

Avatar Url Robert Manger (autor)

Citiraj ovu publikaciju

Rudec, Tomislav; Manger, Robert
On the Competitiveness of a Modified Work Function Algorithm for Solving the On-Line k-Server Problem // 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 (ur.).
Zagreb: University Computing Centre, 2008. str. 779-784 (predavanje, međunarodna recenzija, cjeloviti rad (in extenso), znanstveni)
Rudec, T. & Manger, R. (2008) On the Competitiveness of a Modified Work Function Algorithm for Solving the On-Line k-Server Problem. U: Lužar-Stiffler, V., Dobrić Hljuz, V. & Bekić, Z. (ur.)Proceedings of the 30th International Conference on Information Technology Interfaces (ITI 2008 - Cavtat, Croatia, June 23-26, 2008).
@article{article, year = {2008}, pages = {779-784}, keywords = {on-line problems, on-line algorithms, k-server problem, work function algorithm (WFA), moving windows, competitiveness}, title = {On the Competitiveness of a Modified Work Function Algorithm for Solving the On-Line k-Server Problem}, keyword = {on-line problems, on-line algorithms, k-server problem, work function algorithm (WFA), moving windows, competitiveness}, publisher = {University Computing Centre}, publisherplace = {Cavtat, Hrvatska} }