文章基本信息

标题：Barrier Coverage with Non-uniform Lengths to Minimize Aggregate Movements
本地全文：下载
作者：Serge Gaspers ; Joachim Gudmundsson ; Juli{\'a}n Mestre 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：92
页码：37:1-37:13
DOI：10.4230/LIPIcs.ISAAC.2017.37
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Given a line segment I=[0,L], the so-called barrier, and a set of n sensors with varying ranges positioned on the line containing I, the barrier coverage problem is to move the sensors so that they cover I, while minimising the total movement. In the case when all the sensors have the same radius the problem can be solved in O(n log n) time (Andrews and Wang, Algorithmica 2017). If the sensors have different radii the problem is known to be NP-hard to approximate within a constant factor (Czyzowicz et al., ADHOC-NOW 2009). We strengthen this result and prove that no polynomial time \rho^{1-\epsilon}-approximation algorithm exists unless P=NP, where \rho is the ratio between the largest radius and the smallest radius. Even when we restrict the number of sensors that are allowed to move by a parameter k, the problem turns out to be W[1]-hard. On the positive side we show that a ((2+\epsilon)\rho+2/\epsilon)-approximation can be computed in O(n^3/\epsilon^2) time and we prove fixed-parameter tractability when parameterized by the total movement assuming all numbers in the input are integers.
关键词：Barrier coverage; Sensor movement; Approximation; Parameterized complexity