crta
Hrvatska znanstvena Sekcija img
bibliografija
3 gif
 Naslovna
 O projektu
 FAQ
 Kontakt
4 gif
Pregledavanje radova
Jednostavno pretraživanje
Napredno pretraživanje
Skupni podaci
Upis novih radova
Upute
Ispravci prijavljenih radova
Ostale bibliografije
Slični projekti
 Bibliografske baze podataka

Pregled bibliografske jedinice broj: 763946

Časopis

Autori: Goran Martinović; Domagoj Matijević; Domagoj Ševerdija
Naslov: Efficient Parallel Implementations Of Approximation Algorithms For Guarding 1.5d Terrains
Izvornik: Croatian Operational Research Review (1848-0225) 6 (2015), 1; 71-78
Vrsta rada: članak
Ključne riječi: 1.5D terrain guarding; linear programming; CUDA; approximation algorithm
Sažetak:
In the 1.5D terrain guarding problem, an x- monotone polygonal line is defined by k vertices and a G set of terrain points, i.e. guards, and a N set of terrain points which guards are to observe (guard). This involves a weighted version of the guarding problem where guards G have weights. The goal is to determine a minimum weight subset of G to cover all the points in N, including a version where points from N have demands. Furthermore, another goal is to determine the smallest subset of G, such that every point in N is observed by the required number of guards. Both problems are NP-hard and have a factor 5 approximation [3, 4]. This paper will show that if the (1 + ϵ)- approximate solver for the corresponding linear program is a computer, for any ϵ > 0, an extra 1 +ϵ factor will appear in the final approximation factor for both problems. A comparison will be carried out the parallel implementation based on GPU and CPU threads with the Gurobi solver, leading to the conclusion that the respective algorithm outperforms the Gurobi solver on large and dense inputs typically by one order of magnitude.
Izvorni jezik: ENG
Rad je citiran u
bazama podataka:
Web of Science: Emerging Sources Citation Index
Kategorija: Znanstveni
Znanstvena područja:
Matematika
URL Internet adrese: http://hrcak.srce.hr/ojs/index.php/crorr/article/view/2798
URL cjelovitog teksta:
Google Scholar: Efficient Parallel Implementations Of Approximation Algorithms For Guarding 1.5d Terrains
Upisao u CROSBI: Domagoj Severdija (dseverdi@mathos.hr), 2. Lip. 2015. u 15:20 sati



Verzija za printanje   za tiskati


upomoc
foot_4