Improved Approximations for Guarding 1.5-Dimensional Terrains

Elbassioni, Khaled; Krohn, Erik; Matijevic, Domagoj; Mestre, Julian; Severdija, Domagoj

doi:10.4230/LIPIcs.STACS.2009.1841

Document

Improved Approximations for Guarding 1.5-Dimensional Terrains

Authors Khaled Elbassioni, Erik Krohn, Domagoj Matijevic, Julian Mestre, Domagoj Severdija

Part of: Volume: 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Symposium on Theoretical Aspects of Computer Science (STACS)
License: Creative Commons Attribution-NoDerivs 3.0 Unported license
Publication Date: 2009-02-19

PDF

File

PDF

LIPIcs.STACS.2009.1841.pdf

Filesize: 169 kB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2009.1841
URN: urn:nbn:de:0030-drops-18410

Subject Classification

Keywords

Covering problems
Guarding 1.5-terrains
Approximation algorithms
Linear programming
Totally balanced matrices

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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 (J. King, 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.

Cite As Get BibTex

Khaled Elbassioni, Erik Krohn, Domagoj Matijevic, Julian Mestre, and Domagoj Severdija. Improved Approximations for Guarding 1.5-Dimensional Terrains. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 361-372, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009) https://doi.org/10.4230/LIPIcs.STACS.2009.1841

Author Details

Khaled Elbassioni

Erik Krohn

Domagoj Matijevic

Julian Mestre

Domagoj Severdija

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail