License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.37
URN: urn:nbn:de:0030-drops-82591
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8259/
Gaspers, Serge ;
Gudmundsson, Joachim ;
Mestre, Julián ;
Rümmele, Stefan
Barrier Coverage with Non-uniform Lengths to Minimize Aggregate Movements
Abstract
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.
BibTeX - Entry
@InProceedings{gaspers_et_al:LIPIcs:2017:8259,
author = {Serge Gaspers and Joachim Gudmundsson and Juli{\'a}n Mestre and Stefan R{\"u}mmele},
title = {{Barrier Coverage with Non-uniform Lengths to Minimize Aggregate Movements}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {37:1--37:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-054-5},
ISSN = {1868-8969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8259},
URN = {urn:nbn:de:0030-drops-82591},
doi = {10.4230/LIPIcs.ISAAC.2017.37},
annote = {Keywords: Barrier coverage, Sensor movement, Approximation, Parameterized complexity}
}
|
Keywords: |
|
Barrier coverage, Sensor movement, Approximation, Parameterized complexity |
|
Collection: |
|
28th International Symposium on Algorithms and Computation (ISAAC 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
07.12.2017 |
