An Improved PTAS for Covering Targets with Mobile Sensors
share
This paper considers a movement minimization problem for mobile sensors. Given a set of n point targets, the k-Sink Minimum Movement Target Coverage Problem is to schedule mobile sensors, initially located at k base stations, to cover all targets minimizing the total moving distance of the sensors. We present a polynomial-time approximation scheme for finding a (1+ϵ) approximate solution running in time n^O(1/ϵ) for this problem when k, the number of base stations, is constant. Our algorithm improves the running time exponentially from the previous work that runs in time n^O(1/ϵ^2), without any target distribution assumption. To devise a faster algorithm, we prove a stronger bound on the number of sensors in any unit area in the optimal solution and employ a more refined dynamic programming algorithm whose complexity depends only on the width of the problem.
READ FULL TEXT