检索结果-内蒙古大学图书馆

Thek$k$-prize-collecting coverage problem by aligned disks

International Transactions in Operational Research 2025年

作者： Hao Zhang Xiya Zheng Zhonghao Liu Xiaofei Liu School of Information Science and Engineering Yunnan University Kunming 650500 China School of Mathematics and Statistics Yunnan University Kunming 650500 China

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 set D ′ $\mathcal {D}^{\prime }$ of disks whose centers are all in S $S$ such that the total profit of the users covered by D ′ $\mathcal {D}^{\prime }$ is at least k $k$ , and the objective value, which consists of the total cost of the disks in D ′ $\mathcal {D}^{\prime }$ plus the total penalty of the uncovered users in U ∖ U ⁡ ( D ′ ) $U\setminus U(\mathcal {D}^{\prime })$ , is minimized, where the cost of disk D $D$ is r ⁢ ( 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 is N ⁢ 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.

关键词： disk coverage problem k$k$-prize-collecting dynamic programming fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：