engleski

Improved Approximation Agorithms for 1.5D Terrain Guarding T ERRAIN GUARDING

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.

approximation algorithms; CUDA; 1.5D terrain guarding; primal-dual algorithms; covering-packing problems; visibility problem

nije evidentirano