Pretražite po imenu i prezimenu autora, mentora, urednika, prevoditelja

Napredna pretraga

Pregled bibliografske jedinice broj: 541654

Brzi algoritmi za rješavanje problema k poslužitelja zasnovani na tokovima u mrežama


Rudec, Tomislav
Brzi algoritmi za rješavanje problema k poslužitelja zasnovani na tokovima u mrežama, 2011., doktorska disertacija, Prirodoslovno-matematički fakultet, Matematički odsjek, Zagreb


CROSBI ID: 541654 Za ispravke kontaktirajte CROSBI podršku putem web obrasca

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


Projekt / tema
037-0362980-2774 - Distribuirani algoritmi za pronalaženje optimalnih putova u grafovima (Robert Manger, )

Ustanove
Prirodoslovno-matematički fakultet, Matematički odjel, Zagreb

Profili:

Avatar Url Tomislav Rudec (autor)

Avatar Url Robert Manger (mentor)

Citiraj ovu publikaciju

Rudec, Tomislav
Brzi algoritmi za rješavanje problema k poslužitelja zasnovani na tokovima u mrežama, 2011., doktorska disertacija, Prirodoslovno-matematički fakultet, Matematički odsjek, Zagreb
Rudec, T. (2011) 'Brzi algoritmi za rješavanje problema k poslužitelja zasnovani na tokovima u mrežama', doktorska disertacija, Prirodoslovno-matematički fakultet, Matematički odsjek, Zagreb.
@phdthesis{phdthesis, author = {Rudec, T.}, year = {2011}, pages = {133}, keywords = {on-line problems, k-server problem, optimal off-line algorithm, work function algorithm, implementation, network flow}, title = {Fast algorithms for solving the k-server problem based on network flows}, keyword = {on-line problems, k-server problem, optimal off-line algorithm, work function algorithm, implementation, network flow}, publisherplace = {Zagreb} }