Approximation algorithm for sweep coverage on graph

• Remarked on the flaw of approximation algorithms in the previous study and proposed a 3-approximation algorithm.
• Generalized the proposed algorithm when vertices of the graph have different sweep periods and processing times.
• Inapproximability result is proved for the sweep coverage problem with mobile sensors having different velocities.

The objective of sweep coverage problem is to find the minimum number of mobile sensors to ensure periodic monitoring for a given set of points of interest. In this paper we remark on the flaw of the approximation algorithms proposed in paper [16] for sweep coverage with mobile sensors and propose a 3-approximation algorithm to guarantee sweep coverage of vertices of a graph. We propose a solution of the problem when vertices of a graph have different sweep periods and processing times. The approximation factor of the proposed solution is O(log⁡ρ)O(log⁡ρ), where ρ   is the ratio of the maximum and minimum sweep periods among the vertices. We prove that if velocities of the mobile sensors are different, it is impossible to give any constant factor approximation algorithm to solve the sweep coverage problem unless P=NPP=NP.