Pregled bibliografske jedinice broj: 321497
A network flow implementation of a modified work function algorithm for solving the k-server problem
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: Slovensko društvo informatika, 2007. str. 83-90 (predavanje, međunarodna recenzija, cjeloviti rad (in extenso), znanstveni)
CROSBI ID: 321497 Za ispravke kontaktirajte CROSBI podršku putem web obrasca
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 : Slovensko društvo informatika, 2007, 83-90
Skup
International Symposium on Operational Research in Slovenia (8 ; 2007)
Mjesto i datum
Nova Gorica, Slovenija, 26.09.2007. - 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
Projekti:
037-0362980-2774 - Distribuirani algoritmi za pronalaženje optimalnih putova u grafovima (Manger, Robert, MZOS ) ( CroRIS)
165-0361621-2000 - Distribuirano računalno upravljanje u transportu i industrijskim pogonima (Hocenski, Željko, MZO ) ( CroRIS)
Ustanove:
Prirodoslovno-matematički fakultet, Matematički odjel, Zagreb,
Fakultet elektrotehnike, računarstva i informacijskih tehnologija Osijek
