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.