Improved Approximation Algorithms for 1.5D Terrain Guarding (CROSBI ID 547289)
Prilog sa skupa u zborniku | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Elbassioni, Khaled ; Krohn, Erik ; Matijević, Domagoj ; Mestre, Julian ; Ševerdija, Domagoj
engleski
Improved Approximation Algorithms for 1.5D Terrain Guarding
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.
Terrain Guarding; Approximation Algorithms; Totally Balanced Matrices
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o prilogu
361-372.
2009.
objavljeno
Podaci o matičnoj publikaciji
Proceedings of the 26th International Symposium on Theoreticas Aspects of Computer Science
Susanne Albers, Jean-Yves Marion
Freiburg: IBFI Schloss Dagstuhl
978-3-939897-09-5
Podaci o skupu
Symposium on Theoretical Aspects of Computer Science
predavanje
01.01.2009-01.01.2009
Freiburg, Njemačka