Article ID Journal Published Year Pages File Type
427113 Information Processing Letters 2015 7 Pages PDF
Abstract

•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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,