Approximation algorithm for the minimum capacitated sweep coverage problem

Source abstract

In this paper, we propose a new sweep coverage problem: The Minimum Capacitated Sweep Cover (MinCapSC) problem, the goal of which is to design routes for the minimum number of mobile sensors such that each target point is visited by a mobile sensor in every time period of at most [Formula: see text], and each mobile sensor is responsible for at most [Formula: see text] target points. We designed a [Formula: see text]-approximation algorithm.