Barrier coverage with non-uniform lengths to minimize aggregate movements

DOI10.4230/LIPICS.ISAAC.2017.37zbMATH Open1457.68290OpenAlexW2962758055MaRDI QIDQ5136256FDOQ5136256

Authors Serge Gaspers, Joachim Gudmundsson, Julián Mestre, Stefan Rümmele

Publication date 25 November 2020

Full work available at URL https://arxiv.org/abs/1709.10285

zbMATH Keywords

approximationparameterized complexitybarrier coveragesensor movement

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

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(nlogn)$ 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 $h{o}^{1-varepsilon}$-approximation algorithm exists unless $P=NP$, where $ho$ 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+varepsilon)ho+2/varepsilon)$-approximation can be computed in $O(n^3/varepsilo{n}^2)$ time and we prove fixed-parameter tractability when parameterized by the total movement assuming all numbers in the input are integers.

Recommendations

• Barrier Coverage with Uniform Radii in 2D

Cites work

• Complexity of barrier coverage with relocatable sensors in the plane
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Perfect Code is \(W[1]\)-complete

Cited in

(4)

• On the complexity of and algorithms for min-max target coverage on a line boundary
• Barrier Coverage with Uniform Radii in 2D
• Complexity of barrier coverage with relocatable sensors in the plane
• Barrier coverage problem in 2D

This page was built for publication: Barrier coverage with non-uniform lengths to minimize aggregate movements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136256)