Improved approximations for guarding 1.5-dimensional terrains

Khaled Elbassioni, Erik Krohn, Domagoj Matijević, Julián Mestre, Domagoj Ševerdija

Research output: Contribution to journalArticlepeer-review

27 Scopus citations

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 (see King in Proceedings of the 13th Latin American Symposium on Theoretical Informatics, pp. 629-640, 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 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.

Original languageBritish English
Pages (from-to)451-463
Number of pages13
JournalAlgorithmica (New York)
Volume60
Issue number2
DOIs
StatePublished - Jun 2011

Keywords

  • Approximation algorithms
  • Geometric covering problems
  • Terrain guarding
  • Totally balanced matrices

Fingerprint

Dive into the research topics of 'Improved approximations for guarding 1.5-dimensional terrains'. Together they form a unique fingerprint.

Cite this