Naslov
Guarding 1.5D Terrains with Demands

Autori
Elbassioni, Khaled ; Matijević, Domagoj ; Ševerdija, Domagoj

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Izvornik
26th European Workshop on Computational Geometry, Workshop Proceedings / Jan Vahrenhold - Dortmund : Technische Universitat Dortmund, 2010, 133-136

Skup
26th European Workshop on Computational Geometry

Mjesto i datum
Dortmund, Njemačka, 22.04.2010. - 24.04.2010

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
čuvanje 1.5D terena; LP relaksacija; zahtjevi
(1.5D terrain guarding; LP relaxation; demands)

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA