Brzi algoritmi za rješavanje problema k poslužitelja zasnovani na tokovima u mrežama (CROSBI ID 367785)
Ocjenski rad | doktorska disertacija
Podaci o odgovornosti
Rudec, Tomislav
Manger, Robert
hrvatski
Brzi algoritmi za rješavanje problema k poslužitelja zasnovani na tokovima u mrežama
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.
on-line problemi; problem k poslužitelja; optimalni off-line algoritam; algoritam radne funkcije; implementacija; tok u mreži
nije evidentirano
engleski
Fast algorithms for solving the k-server problem based on network flows
nije evidentirano
on-line problems; k-server problem; optimal off-line algorithm; work function algorithm; implementation; network flow
nije evidentirano
Podaci o izdanju
133
04.04.2011.
obranjeno
Podaci o ustanovi koja je dodijelila akademski stupanj
Prirodoslovno-matematički fakultet, Zagreb
Zagreb