An improved approximation algorithm for the $ k $ -prize-collecting minimum power cover problem
Wencheng Wang, Binhui Cheng, Jianglin Li, Yinhua Chen, Tongquan Zhang · Journal of Industrial and Management Optimization · 2023
In this paper, we consider the $ k $-prize-collecting minimum power cover problem ($ k $-PCPC), which is defined as follows. Given a set $ X = \{x_1, x_2, $ $ \cdots, x_n\} $ of $ n $ points and a set $ S = \{s_1, s_2, \cdots, s_m\} $ of $ m $ sensors on the plane $ \mathbb{R}^2 $, an integer $ k $ satisfying $ 0 \leq k \leq n $ and a penalty function $ \pi: X \rightarrow \mathbb{R}_0^{+} $, each sensor $ s\in S $ can adjust its power $ p(s) $ and the covering range, which is a disk of radius $ r(s) $ satisfying $ p(s) = c\cdot r(s)^\alpha $, where $ \alpha\geq 1 $ and $ c>0 $ are constants. We are asked to determine a set of disks $ \mathcal{F} $ such that at least $ k $ points are covered, where the center of any disk in $ \mathcal{F} $ is a sensor. The objective is to minimize the total power of the set of disks $ \mathcal{F} $ plus the penalty of $ R $, where $ R $ is the set of points that are not covered by $ \mathcal{F} $. It has been proven that this problem is NP-hard and admits a $ 3^\alpha $-approximation algorithm. By using some properties of relaxed independent sets and combining the guessing technique and the primal-dual method, we design an $ O(\alpha) $-approximation algorithm. Numerical experiments are tested to evaluate the performance of the $ 3^\alpha $-approximation algorithm and our new algorithm.