Improved Approximations for Guarding 1.5‐Dimensional Terrains

Improved Approximations for Guarding 1.5‐Dimensional Terrains

0.00 Avg rating0 Votes
Article ID: iaor20114261
Volume: 60
Issue: 2
Start Page Number: 451
End Page Number: 463
Publication Date: Jun 2011
Journal: Algorithmica
Authors: , , , ,
Keywords: programming: linear
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 previous 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.

Reviews

Required fields are marked *. Your email address will not be published.