The K$K$‐prize‐collecting coverage problem by aligned disks
Hao Zhang, Xiya Zheng, Zhonghao Liu, Xiaofei Liu · International Transactions in Operational Research · 2025
Abstract In this paper, we study the ‐prize‐collecting coverage problem by using aligned disks. Suppose is a set of users, is a horizontal line on the plane, and is a set of points on the line , where each user corresponds to a coordinate point, with an associated profit and an uncovered penalty. The problem is to select a set of disks whose centers are all in such that the total profit of the users covered by is at least , and the objective value, which consists of the total cost of the disks in plus the total penalty of the uncovered users in , is minimized, where the cost of disk is , is an attenuation factor, is the radius of disk , and is a given profit bound. We first prove that this problem is ‐hard even when all users are located on line , 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.