Title: Minimizing total sensor movement for barrier coverage by non-uniform sensors on a line
\n(extended version of Mark’s upcoming talk at ALGOSENSORS in Patras, Greece)
\nSpeaker: Mark Thom, PhD student, Optimization Research Group
\nLocation & time: B543, Fri. Sept. 11, 2015, 12:00pm – 12:50pm <\/p>\n
Abstract: Barrier coverage is a cost effective approach to intruder detection
\napplications. It consists of monitoring the perimeter, or barrier, of
\nan area by placing sensors at appropriate locations on the barrier. In
\nthis talk, we consider a restricted version of the barrier coverage
\nproblem in which the area of coverage is a line segment and the
\nsensors are points with varying detection ranges that lie in initial
\npositions disjoint to the line segment. Sensors are moved along the
\nline containing the line segment to their final positions in the
\ncoverage, and the distances moved by each sensor are summed,
\ndetermining the cost of the coverage. The objective is to find the
\ncoverage of least cost.\u00a0 We sketch a proof of the NP-hardness of the
\nrestricted problem and outline a polynomial-time approximation scheme
\nthat produces barrier coverages of cost arbitrarily close to that of
\nan optimal solution. Everyone is welcome, no prior knowledge of
\napproximation algorithms or NP-hardness is assumed.<\/p>\n","protected":false},"excerpt":{"rendered":"
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, … Continue reading