Improved Approximations for Guarding 1.5-Dimensional Terrains
Improved Approximations for Guarding 1.5-Dimensional Terrains
复制标题
改进了保护 1.5 维地形的近似值
作者：
Khaled M. Elbassioni;Erik Krohn;Domagoj Matijević;Julián Mestre;Domagoj Ševerdija
对于在1.5维地形上放置最少警卫的问题，我们提出了一个4-近似算法，使得地形上的每个点都能被至少一个警卫看到。这比以前的最佳逼近因子5有所改进(见King在2006年第13届拉丁美洲理论信息学研讨会论文集上，第629-640页)。与以往的大多数方法不同，我们的方法是基于对相应覆盖问题的线性规划松弛进行舍入。除了分析的简单性(主要依赖于将LP的约束矩阵分解成完全平衡的矩阵)之外，与以前的工作不同，我们的算法推广到基本问题的加权和部分版本。
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.