Improved Approximations for Guarding 1.5-Dimensional Terrains
| Autor: | Julián Mestre, Domagoj Matijevic, Khaled Elbassioni, Erik Krohn, Domagoj Ševerdija |
|---|---|
| Přispěvatelé: | Loria, Publications, Susanne Albers and Jean-Yves Marion |
| Jazyk: | angličtina |
| Rok vydání: | 2009 |
| Předmět: |
000 Computer science
knowledge general works General Computer Science Linear programming Applied Mathematics Rounding Constrained optimization terrain guarding approximation algorithms totally balanced matrices geometric covering problems Approximation algorithm Graph theory [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] Computer Science Applications Linear programming relaxation [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO] Computer Science Theory of computation Round-off error Algorithm Computer Science(all) Mathematics |
| Zdroj: | Scopus-Elsevier |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|