Napredna pretraga

Pregled bibliografske jedinice broj: 673213

Unaprijeđeni aproksimacijski algoritmi za pokrivanje 1.5D terena


Ševerdija, Domagoj
Unaprijeđeni aproksimacijski algoritmi za pokrivanje 1.5D terena 2013., doktorska disertacija, Elektrotehnički fakultet Osijek, Osijek


Naslov
Unaprijeđeni aproksimacijski algoritmi za pokrivanje 1.5D terena
(Improved Approximation Agorithms for 1.5D Terrain Guarding T ERRAIN GUARDING)

Autori
Ševerdija, Domagoj

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, doktorska disertacija

Fakultet
Elektrotehnički fakultet Osijek

Mjesto
Osijek

Datum
13.12

Godina
2013

Stranica
149

Mentor
Martinović, Goran

Neposredni voditelj
Martinović, Goran ; Matijević, Domagoj

Ključne riječi
Aprokimacijski algoritmi; CUDA; čuvanje 1.5D terena; primal-dual algoritmi; problem pakiranja i pokrivanja; problem vidljivosti
(Approximation algorithms; CUDA; 1.5D terrain guarding; primal-dual algorithms; covering-packing problems; visibility problem)

Sažetak
Ovaj doktorski rad proučava poboljšane aproksimacije za nekoliko inačica problema čuvanja 1.5D terena. Ulaz problema je poligonalna x- monotona linija na kojem je odabran skup čuvara i skup klijenata. Cilj je odrediti optimalni broj čuvara koji će pokriti sve klijente. U doktorskom radu su predstavljeni aproksimacijski algoritmi za varijante kad čuvari imaju pridružene težine/cijene odnosno kad klijenti zahtjevaju robusnije čuvanje, dakle, imaju zahtjev na broj čuvara koji ih moraju pokrivati. U inačici problema s težinama promatra se i problem parcijalnog pokrivanja. U svim inačicama problema predstavljen je prvi aproksimacijski algoritam konstantne aproksimacije i u trenutku pisanja predstavlja state-of-the-art rezultat za te probleme. Korištenjem tehnike zaokruživanja rješenja linearnog programa odgovarajućeg problema čuvanja 1.5D terena ispostavlja se da sve inačice problema promatranih u doktorskom radu mogu aproksimirati unutar faktora 5 do na neku proizvoljno malu aditivnu grešku. Kako rješavatelj linearnog programa predstavlja osnovni dio predstavljenih algoritama za čuvanje 1.5D terena, promatra se RAM i CUDA model implementacije brzog aproksimativnog rješavanja linearnog programa posebne klase problema zvanih problemi pokrivanja i pakiranja. Eksperimentalnom analizom uspoređuje se aproksimacijska shema za rješavanje linearnih programa problema pakiranja i pokrivanja na nekoliko tipova ulaza na jednoprocesorskoj i CUDA omogućenoj platformi te s već postojećim rješavateljem linearnih programa. Za teorijsku analizu vremena izvršavanja CUDA modela uzima se PRAM model čija se korespondencija s CUDA platformom potvrđuje eksperimentima. Kao model implementacije u ovom radu se predlaže ugradnja )1 + e) aproksimativnih rješavatelja za rješavanje linearnog programa kao podrutine za aproksimacijske algoritme čuvanja 1.5D terena što uvodi dodatni multiplikativni faktor pogreške 1+ e u aproksimacijskim faktorima, ali daje eksplicitnu ovisnost o parametru 1/e u vremenima izvršavanja aproksimacijskih algoritama.

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo



POVEZANOST RADA


Projekt / tema
165-0361621-2000 - Distribuirano računalno upravljanje u transportu i industrijskim pogonima (Željko Hocenski, )
165-0362980-2002 - Postupci raspoređivanja u samoodrživim raspodijeljenim računalnim sustavima (Goran Martinović, )

Ustanove
Fakultet elektrotehnike, računarstva i informacijskih tehnologija Osijek

Autor s matičnim brojem:
Domagoj Ševerdija, (300556)