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...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.