Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/inria-00359652
Contributor : Publications Loria <>
Submitted on : Monday, February 9, 2009 - 10:06:43 AM
Last modification on : Thursday, September 20, 2018 - 7:54:02 AM
Long-term archiving on: : Tuesday, June 8, 2010 - 10:04:28 PM

File

30-elbassioni.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00359652, version 1

Collections

Citation

Khaled Elbassioni, Erik Krohn, Domagoj Matijevic, Julián Mestre, Domagoj Severdija. Improved Approximations for Guarding 1.5-Dimensional Terrains. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.361-372. ⟨inria-00359652⟩

Share

Metrics

Record views

278

Files downloads

450