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