TY - JOUR
T1 - Improved approximations for guarding 1.5-dimensional terrains
AU - Elbassioni, Khaled
AU - Krohn, Erik
AU - Matijević, Domagoj
AU - Mestre, Julián
AU - Ševerdija, Domagoj
PY - 2011/6
Y1 - 2011/6
N2 - 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 previous best approximation factor of 5 (see King in Proceedings of the 13th Latin American Symposium on Theoretical Informatics, pp. 629-640, 2006). 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.
AB - 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 previous best approximation factor of 5 (see King in Proceedings of the 13th Latin American Symposium on Theoretical Informatics, pp. 629-640, 2006). 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.
KW - Approximation algorithms
KW - Geometric covering problems
KW - Terrain guarding
KW - Totally balanced matrices
UR - http://www.scopus.com/inward/record.url?scp=79953166874&partnerID=8YFLogxK
U2 - 10.1007/s00453-009-9358-4
DO - 10.1007/s00453-009-9358-4
M3 - Article
AN - SCOPUS:79953166874
SN - 0178-4617
VL - 60
SP - 451
EP - 463
JO - Algorithmica (New York)
JF - Algorithmica (New York)
IS - 2
ER -