@inproceedings{4736683a52164ad884a5fc33105d90c1,
title = "Improved approximations for guarding 1.5-dimensional terrains",
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 (see [14]). 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.",
keywords = "Approximation algorithms, Covering problems, Guarding 1.5-terrains, Linear programming, Totally balanced matrices",
author = "Khaled Elbassioni and Erik Krohn and Domagoj Matijevi{\'c} and Juli{\'a}n Mestre and Domagoj {\v S}everdija",
year = "2009",
language = "British English",
isbn = "9783939897095",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
pages = "361--371",
booktitle = "STACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science",
note = "26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009 ; Conference date: 26-02-2009 Through 28-02-2009",
}