Nalazite se na CroRIS probnoj okolini. Ovdje evidentirani podaci neće biti pohranjeni u Informacijskom sustavu znanosti RH. Ako je ovo greška, CroRIS produkcijskoj okolini moguće je pristupi putem poveznice www.croris.hr
izvor podataka: crosbi !

Efficient Parallel Implementations Of Approximation Algorithms For Guarding 1.5d Terrains (CROSBI ID 218770)

Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija

Goran Martinović ; Domagoj Matijević ; Domagoj Ševerdija Efficient Parallel Implementations Of Approximation Algorithms For Guarding 1.5d Terrains // Croatian operational research review, 6 (2015), 1; 71-78

Podaci o odgovornosti

Goran Martinović ; Domagoj Matijević ; Domagoj Ševerdija

engleski

Efficient Parallel Implementations Of Approximation Algorithms For Guarding 1.5d Terrains

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.

1.5D terrain guarding; linear programming; CUDA; approximation algorithm

nije evidentirano

nije evidentirano

nije evidentirano

nije evidentirano

nije evidentirano

nije evidentirano

Podaci o izdanju

6 (1)

2015.

71-78

objavljeno

1848-0225

1848-9931

Povezanost rada

Matematika

Poveznice
Indeksiranost