In this paper we give approximation algorithms and inapproximability results for various asymmetric k-center with minimum coverage problems.
It is easy to know that the Minimum-Delay POIs Coverage problem is equivalent to the minimum max-min trajectory schedule problem.
In this section, we study the Minimum-Delay POIs Coverage problem with the restriction on the start positions of mobile sensors, and propose an algorithm for the problem.
In Section 4, we propose the Stretched Searching SSR algorithm for the Minimum-Delay POIs Coverage problem with restriction on start positions of mobile sensors.
In this section, we propose an effective algorithm, the SSR algorithm for the Minimum-Delay POIs Coverage problem with the restriction on the start positions of mobile sensors.
The goal of the Minimum-Delay POIs Coverage problem is scheduling the given number of mobile sensors to monitor all POIs in the region and minimizing the delay.
Based on the given Euclidean distance between any two points, finding a coverage scheme for the Minimum-Delay POIs Coverage problem is equivalent to finding a set of trajectories which can pass by all the POIs.
Definition 3. Minimum-Delay POIs Coverage in mobile wireless sensor networks problem: Given k mobile sensors and the deployments of m POIs, the Minimum-Delay POIs Coverage problem is to schedule k mobile sensors to scan POIs along different trajectories such that the delay of the POIs coverage is minimized.
Apparently, the Minimum-Delay POIs Coverage problem can be transformed to the problem of minimizing the maximal trajectory of mobile sensors: given k mobile sensors, find a set of k trajectories to pass all POIs such that the maximum length among all k trajectories is minimized.
In this section, we will propose two algorithms for the Minimum-Delay POIs Coverage problem to deal with the scenario that the mobile sensors are not restricted to start sweeping from the determined positions, which is more flexible in practical applications.
