License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2009.1841
URN: urn:nbn:de:0030-drops-18410
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/1841/
Go to the corresponding LIPIcs Volume Portal

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

Improved Approximations for Guarding 1.5-Dimensional Terrains

pdf-format:
09001.ElbassioniKhaled.1841.pdf (0.2 MB)

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.

BibTeX - Entry

@InProceedings{elbassioni_et_al:LIPIcs:2009:1841,
  author =	{Khaled Elbassioni and Erik Krohn and Domagoj Matijevic and Julian Mestre and Domagoj Severdija},
  title =	{{Improved Approximations for Guarding 1.5-Dimensional Terrains}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{361--372},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Susanne Albers and Jean-Yves Marion},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/1841},
  URN =		{urn:nbn:de:0030-drops-18410},
  doi =		{10.4230/LIPIcs.STACS.2009.1841},
  annote =	{Keywords: Covering problems, Guarding 1.5-terrains, Approximation algorithms, Linear programming, Totally balanced matrices}
}

Keywords: Covering problems, Guarding 1.5-terrains, Approximation algorithms, Linear programming, Totally balanced matrices
Collection: 26th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2009
Date of publication: 19.02.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI