An Approximation Algorithm for Min-Sum Movement Target Coverage

Source abstract

In this paper, we study an approximation algorithm for the problem of Min-Sum Movement Target Coverage (MinSMTC). Given [Formula: see text] targets [Formula: see text] and [Formula: see text] mobile sensors [Formula: see text] on the plane, each sensor has a coverage radius [Formula: see text] and can cover those targets within distance [Formula: see text] from it. The sensors, at their original locations, might not be able to cover all targets. The goal of MinSMTC is to move sensors to new locations such that all targets can be covered and the total movement distance is minimized. We show that even determining the feasibility of the problem is NP-complete. Then, we present a [Formula: see text]-approximation algorithm as long as the algorithm can return a feasible solution, where [Formula: see text] is a parameter related to the number of targets that can be covered by a sensor at a candidate destination location.