Naslov
Improved Approximation Algorithms for 1.5D Terrain Guarding

Autori
Elbassioni, Khaled ; Krohn, Erik ; Matijević, Domagoj ; Mestre, Julian ; Ševerdija, Domagoj

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

Izvornik
Proceedings of the 26th International Symposium on Theoreticas Aspects of Computer Science / Susanne Albers, Jean-Yves Marion - Freiburg : IBFI Schloss Dagstuhl, 2009, 361-372

ISBN
978-3-939897-09-5

Skup
Symposium on Theoretical Aspects of Computer Science

Mjesto i datum
Freiburg, Njemačka, 02.2009

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
Terrain Guarding; Approximation Algorithms; Totally Balanced Matrices

Sažetak
We present a 4-approximation algorithm for the problem of placing the fewest guards on a 1.5D terrain so that every point of the terrain is seen by at least one guard. This improves on the currently best approximation factor of 5. Unlike most of the previous techniques, our method is based on rounding the linear programming relaxation of the corresponding covering problem. Besides the simplicity of the analysis, which mainly relies on decomposing the constraint matrix of the LP into totally balanced matrices, our algorithm, unlike previous work, generalizes to the weighted and partial versions of the basic problem.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA