hrcak mascot   Srce   HID

Croatian Operational Research Review, Vol. 6 No. 1, 2015.

Izvorni znanstveni članak
https://doi.org/10.17535/crorr.2015.0007

Efficient parallel implementations of approximation algorithms for guarding 1.5D terrains

Goran Martinović   ORCID icon orcid.org/0000-0002-7469-6018 ; Faculty of Electrical Engineering, Josip Juraj Strossmayer University of Osijek, Osijek, Croatia
Domagoj Matijević ; Department of Mathematics, Josip Juraj Strossmayer University of Osijek, Osijek, Croatia
Domagoj  Ševerdija ; Department of Mathematics, Josip Juraj Strossmayer University of Osijek, Osijek, Croatia

Puni tekst: engleski, pdf (158 KB) str. 79-89 preuzimanja: 208* citiraj
APA 6th Edition
Martinović, G., Matijević, D. i Ševerdija, D.. (2015). Efficient parallel implementations of approximation algorithms for guarding 1.5D terrains. Croatian Operational Research Review, 6 (1), 79-89. https://doi.org/10.17535/crorr.2015.0007
MLA 8th Edition
Martinović, Goran, et al. "Efficient parallel implementations of approximation algorithms for guarding 1.5D terrains." Croatian Operational Research Review, vol. 6, br. 1, 2015, str. 79-89. https://doi.org/10.17535/crorr.2015.0007. Citirano 19.02.2019.
Chicago 17th Edition
Martinović, Goran, Domagoj Matijević i Domagoj  Ševerdija. "Efficient parallel implementations of approximation algorithms for guarding 1.5D terrains." Croatian Operational Research Review 6, br. 1 (2015): 79-89. https://doi.org/10.17535/crorr.2015.0007
Harvard
Martinović, G., Matijević, D., i Ševerdija, D.. (2015). 'Efficient parallel implementations of approximation algorithms for guarding 1.5D terrains', Croatian Operational Research Review, 6(1), str. 79-89. doi: https://doi.org/10.17535/crorr.2015.0007
Vancouver
Martinović G, Matijević D, Ševerdija D. Efficient parallel implementations of approximation algorithms for guarding 1.5D terrains. Croatian Operational Research Review [Internet]. 2015 [pristupljeno 19.02.2019.];6(1):79-89. doi: https://doi.org/10.17535/crorr.2015.0007
IEEE
G. Martinović, D. Matijević i D.. Ševerdija, "Efficient parallel implementations of approximation algorithms for guarding 1.5D terrains", Croatian Operational Research Review, vol.6, br. 1, str. 79-89, 2015. [Online]. doi: https://doi.org/10.17535/crorr.2015.0007

Sažetak
In the 1.5D terrain guarding problem, an x-monotone polygonal line is de ned 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 fi nal 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.

Ključne riječi
1.5D terrain guarding; linear programming; CUDA; approximation algorithm

Hrčak ID: 138580

URI
https://hrcak.srce.hr/138580

Posjeta: 355 *