Approximation Algorithms for the Minimum Power Partial Cover Problem

摘要

In this paper, we study the minimum power partial cover problem (MinPowerPartCov). Suppose X is a set of points and S is a set of sensors on the plane, each sensor can adjust its power, the covering range of a sensor s with power p(s) is a disk centered at s which has radius r(s) satisfying p(s) = c-r(s)~a. Given an integer k ≤ |X|, the MinPowerPartCov problem is to determine the power assignment on each sensor such that at least k points are covered and the total power consumption is the minimum. We present an approximation algorithm with approximation ratio 3~a, using a local ratio method, which coincides with the best known ratio for the minimum power (full) cover problem. Compared with the paper [9] which studies the MinPowerPartCov problem for a = 2, our ratio improves their ratio from 12 + ε to 9.