Guarding 1.5D Terrains with Demands (CROSBI ID 563799)
Prilog sa skupa u zborniku | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Elbassioni, Khaled ; Matijević, Domagoj ; Ševerdija, Domagoj
engleski
Guarding 1.5D Terrains with Demands
We consider the 1.5D terrain guarding problem in which every point on the terrain that is to be covered has an integer demand associated with it. The goal is to find a minimum cardinality set of guards such that each point is guarded by a number of guards satisfying its demand. We present an algorithm that yields a $6.7$- approximation in the case where the minimum demand $d_{;\min};<5$, and a $3$-approximation otherwise. To the best of our knowledge, this is the first constant factor approximation algorithm for this problem.
1.5D terrain guarding; LP relaxation; demands
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o prilogu
133-136.
2010.
objavljeno
Podaci o matičnoj publikaciji
26th European Workshop on Computational Geometry, Workshop Proceedings
Jan Vahrenhold
Dortmund: Technische Universitat Dortmund
Podaci o skupu
26th European Workshop on Computational Geometry
predavanje
22.04.2010-24.04.2010
Dortmund, Njemačka