Naslov
Brzi algoritmi za rješavanje problema k poslužitelja zasnovani na tokovima u mrežama
(Fast algorithms for solving the k-server problem based on network flows)

Autori
Rudec, Tomislav

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, doktorska disertacija

Fakultet
Prirodoslovno-matematički fakultet, Matematički odsjek

Mjesto
Zagreb

Datum
04.04

Godina
2011

Stranica
133

Mentor
Manger, Robert

Ključne riječi
on-line problemi; problem k poslužitelja; optimalni off-line algoritam; algoritam radne funkcije; implementacija; tok u mreži
(on-line problems; k-server problem; optimal off-line algorithm; work function algorithm; implementation; network flow)

Sažetak
Problem k poslužitelja je problem kombinatorne optimizacije gdje treba odlučiti kako da k pomičnih poslužitelja posluže niz zahtjeva koji se pojavljuju na raznim lokacijama zadanog metričkog prostora. Posluživanje se ostvaruje pomicanjem nekog od poslužitelja na odgovarajuću lokaciju. Pritom se nastoji minimizirati ukupna cijena posluživanja izražena kao zbroj svih udaljenosti koje su poslužitelji prešli. Ova disertacija proučava dva međusobno povezana algoritma za rješavanje problema k poslužitelja: optimalni offline algoritam i online algoritam radne funkcije (WFA). Za oba algoritma razvijeno je po nekoliko novih implementacija koje su zasnovane na tokovima u mrežama i znatno su brže od standardnih implementacija. Ubrzanje je postignuto uporabom drukčijih mrežnih modela, oslanjanjem na posebna svojstva dotičnih mreža, te primjenom drukčijih metoda za traženje toka u mreži. Za svaku predloženu implementaciju disertacija daje dokaz njezine korektnosti. Također, uključeni su konkretni primjeri koji detaljno objašnjavaju sve razmatrane mrežne modele i računske postupke. Pored toga, disertacija sadrži i veliku zbirku eksperimentalnih rezultata. Osim pokusa kojima se mjeri ubrzanje novih implementacija u odnosu na standardne, opisani su i pokusi koji vrednuju WFA po kriteriju cijene posluživanja u odnosu na jednostavne heuristike.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA