DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2009.1841

Improved Approximations for Guarding 1.5-Dimensional Terrains

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

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

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

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)

Copy BibTex To Clipboard

@InProceedings{elbassioni_et_al:LIPIcs.STACS.2009.1841,
  author =	{Elbassioni, Khaled and Krohn, Erik and Matijevic, Domagoj and Mestre, Julian and Severdija, Domagoj},
  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 =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.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}
}

Search Results

Documents authored by Matijevic, Domagoj

Improved Approximations for Guarding 1.5-Dimensional Terrains

Abstract

Cite as

Thanks for your feedback!

Could not send message