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