Improved Approximations for Guarding 1.5-Dimensional Terrains

Khaled Elbassioni, Erik Krohn, Domagoj Matijevic, Julian Mestre & Domagoj Severdija
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 (J. King, 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...