An Improved PTAS for Covering Targets with Mobile Sensors

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

Please sign up or login with your details

Forgot password? Click here to reset