Improved Approximations for Guarding 1.5-Dimensional Terrains

Khaled Elbassioni

Abstract: 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 generalizes to the weighted and

partial versions of the basic problem.