Approximation algorithm for min sweep-period sweep cover with distance constraint

In a sweep cover problem, points of interest (PoIs) are required to be visited by mobile sensors periodically. The time span between two consecutive visits of a PoI is the sweep-period of that PoI. In this paper, we study the min sweep-period sweep cover problem with a distance constraint (MinSPSCDC). Given M mobile sensors with speed a, K base stations and a distance constraint D, the goal of MinSPSCDC is to design routes for the mobile sensors such that the maximum sweep-period is minimized under the condition that every mobile sensor has to visit a base station before traveling distance D. We present an M/M-K+1 & sdot; 2D/D-2d(max)-approximation algorithm for MinSPSCDC, where dmax is the maximum distance between a PoI and a base station.