Napredna pretraga

Pregled bibliografske jedinice broj: 321497

A network flow implementation of a modified work function algorithm for solving the k-server problem


Baumgartner, Alfonzo; Manger, Robert; Hocenski, Željko
A network flow implementation of a modified work function algorithm for solving the k-server problem // Proceedings of the 8th International Symposium on Operational Research in Slovenia (SOR'07) / Zadnik Stirn, Lidija ; Drobne, Samo (ur.).
Ljubljana: Slovenian Society Informatika, 2007. str. 83-90 (predavanje, međunarodna recenzija, cjeloviti rad (in extenso), znanstveni)


Naslov
A network flow implementation of a modified work function algorithm for solving the k-server problem

Autori
Baumgartner, Alfonzo ; Manger, Robert ; Hocenski, Željko

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

Izvornik
Proceedings of the 8th International Symposium on Operational Research in Slovenia (SOR'07) / Zadnik Stirn, Lidija ; Drobne, Samo - Ljubljana : Slovenian Society Informatika, 2007, 83-90

Skup
International Symposium on Operational Research in Slovenia (8 ; 2007)

Mjesto i datum
Nova Gorica, Slovenija, 26.-28.09.2007

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; implementation; network flows; computational complexity

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 describe in detail a network flow implementation of the modified WFA. We also present theoretical estimates and experimental measurements dealing with the computational complexity of the implemented algorithm.

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, )
165-0361621-2000 - Distribuirano računalno upravljanje u transportu i industrijskim pogonima (Željko Hocenski, )

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