The K $K$ ‐prize‐collecting coverage problem by aligned disks

Abstract In this paper, we study the K $K$ ‐prize‐collecting coverage problem by using aligned disks. Suppose U $U$ is a set of users, L $L$ is a horizontal line on the plane, and S $S$ is a set of points on the line L $L$ , where each user corresponds to a coordinate point, with an associated profit and an uncovered penalty. The problem is to select a setD ′ $prime }$ of disks whose centers are all in S $S$ such that the total profit of the users covered byD ′ $prime }$ is at least K $K$ , and the objective value, which consists of the total cost of the disks inD ′ $prime }$ plus the total penalty of the uncovered users inU ∖ U ( D ′ ) $U\setminus U(prime })$ , is minimized, where the cost of disk D $D$ isr ( D ) α $r(D alpha }$ ,α ≥ 1 $\alpha \ge 1$ is an attenuation factor,r ( D ) $r(D)$ is the radius of disk D $D$ , and K $K$ is a given profit bound. We first prove that this problem isN P $NP$ ‐hard even when all users are located on line L $L$ ,α = 1 $\alpha =1$ and the penalty of each user is 0. We present a pseudo‐polynomial‐time algorithm. Finally, we present a fully polynomial time approximation scheme for the problem.