The K$K$‐prize‐collecting coverage problem by aligned disks
Fuente:
Wiley Open Access
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Artículo Open Access |
| Publié: |
Wiley
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1867008530163171328 |
|---|---|
| author | Hao Zhang Xiya Zheng Zhonghao Liu Xiaofei Liu |
| author_facet | Hao Zhang Xiya Zheng Zhonghao Liu Xiaofei Liu Hao Zhang Xiya Zheng Zhonghao Liu Xiaofei Liu |
| collection | Wiley Open Access |
| contents | The K$K$‐prize‐collecting coverage problem by aligned disks Hao Zhang Xiya Zheng Zhonghao Liu Xiaofei Liu International Transactions in Operational Research 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. 10.1111/itor.13608 http://onlinelibrary.wiley.com/termsAndConditions#vor |
| doi_str_mv | 10.1111/itor.13608 |
| format | Artículo Open Access |
| id | wiley_oa_10_1111_itor_13608 |
| institution | Wiley Open Access |
| license_str_mv | http://onlinelibrary.wiley.com/termsAndConditions#vor |
| publishDate | 2025 |
| publisher | Wiley |
| record_format | wiley_oa |
| spellingShingle | The K$K$‐prize‐collecting coverage problem by aligned disks Hao Zhang Xiya Zheng Zhonghao Liu Xiaofei Liu International Transactions in Operational Research The K$K$‐prize‐collecting coverage problem by aligned disks Hao Zhang Xiya Zheng Zhonghao Liu Xiaofei Liu International Transactions in Operational Research 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. 10.1111/itor.13608 http://onlinelibrary.wiley.com/termsAndConditions#vor |
| title | The K$K$‐prize‐collecting coverage problem by aligned disks |
| topic | International Transactions in Operational Research |
| url | https://onlinelibrary.wiley.com/doi/10.1111/itor.13608 |