caa a22 4500 44580467X CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110601xx s 000 0 eng 10.1007/s00453-009-9358-4 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9358-4 Improved Approximations for Guarding 1.5-Dimensional Terrains [Elektronische Daten] [Khaled Elbassioni, Erik Krohn, Domagoj Matijević, Julián Mestre, Domagoj Ševerdija] 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. The Author(s), 2009 Terrain guarding nationallicence Approximation algorithms nationallicence Totally balanced matrices nationallicence Geometric covering problems nationallicence Elbassioni Khaled Max-Planck-Institut für Informatik, Saarbrücken, Germany aut Krohn Erik Department of Computer Science, University of Iowa, Iowa City, USA aut Matijević Domagoj Department of Mathematics, J.J. Strossmayer University of Osijek, Osijek, Croatia aut Mestre Julián Max-Planck-Institut für Informatik, Saarbrücken, Germany aut Ševerdija Domagoj Department of Mathematics, J.J. Strossmayer University of Osijek, Osijek, Croatia aut Algorithmica Springer-Verlag 60/2(2011-06-01), 451-463 0178-4617 60:2<451 2011 60 453 https://doi.org/10.1007/s00453-009-9358-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9358-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Elbassioni Khaled Max-Planck-Institut für Informatik, Saarbrücken, Germany aut NATIONALLICENCE 700 1- Krohn Erik Department of Computer Science, University of Iowa, Iowa City, USA aut NATIONALLICENCE 700 1- Matijević Domagoj Department of Mathematics, J.J. Strossmayer University of Osijek, Osijek, Croatia aut NATIONALLICENCE 700 1- Mestre Julián Max-Planck-Institut für Informatik, Saarbrücken, Germany aut NATIONALLICENCE 700 1- Ševerdija Domagoj Department of Mathematics, J.J. Strossmayer University of Osijek, Osijek, Croatia aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/2(2011-06-01), 451-463 0178-4617 60:2<451 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer