Improved Approximations for Guarding 1.5-Dimensional Terrains

We present a 4-approximation algorithm for the problem of placing a 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. Our method is based on rounding the linear programming relaxation of th...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2008-09
Main Authors: Elbassioni, K, Matijevic, D, Mestre, J, Severdija, D
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Guards
Linear programming
Mathematical analysis
Rounding
Terrain
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a 4-approximation algorithm for the problem of placing a 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. 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.
ISSN:2331-8422