Title: Minimizing total sensor movement for barrier coverage by non-uniform sensors on a line
(extended version of Mark’s upcoming talk at ALGOSENSORS in Patras, Greece)
Speaker: Mark Thom, PhD student, Optimization Research Group
Location & time: B543, Fri. Sept. 11, 2015, 12:00pm – 12:50pm
Abstract: Barrier coverage is a cost effective approach to intruder detection
applications. It consists of monitoring the perimeter, or barrier, of
an area by placing sensors at appropriate locations on the barrier. In
this talk, we consider a restricted version of the barrier coverage
problem in which the area of coverage is a line segment and the
sensors are points with varying detection ranges that lie in initial
positions disjoint to the line segment. Sensors are moved along the
line containing the line segment to their final positions in the
coverage, and the distances moved by each sensor are summed,
determining the cost of the coverage. The objective is to find the
coverage of least cost. We sketch a proof of the NP-hardness of the
restricted problem and outline a polynomial-time approximation scheme
that produces barrier coverages of cost arbitrarily close to that of
an optimal solution. Everyone is welcome, no prior knowledge of
approximation algorithms or NP-hardness is assumed.