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

The K-prize-collecting coverage problem by aligned disks

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2025年

作者： Zhang, Hao Zheng, Xiya Liu, Zhonghao Liu, Xiaofei Yunnan Univ Sch Informat Sci & Engn Kunming 650500 Peoples R China Yunnan Univ Sch Math & Stat Kunming 650500 Peoples R China

In this paper, we study the K-prize-collecting coverage problem by using aligned disks. Suppose U is a set of users, L is a horizontal line on the plane, and S is a set of points on the line I., where each user corresponds to a coordinate point, with an associated profit and an uncovered penalty. The problem is to select a set D of disks whose centers are all in S such that the total profit of the users covered by D' is at least K, and the objective value, which consists of the total cost of the disks in D' plus the total penalty of the uncovered users in U\U (D'), is minimized, where the cost of disk D is r(D)(alpha), alpha >= 1 is an attenuation factor, r(D) is the radius of disk D, and K is a given profit bound. We first prove that this problem is NP-hard even when all users are located on line L, 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-prize-collecting dynamic programming fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

The Bound coverage problem by Aligned disks in L1 Metric 28th

The Bound Coverage Problem by Aligned Disks in L1 Metric

引用

28th International Computing and Combinatorics Conference (COCOON)

作者： Liu, Xiaofei Liu, Zhonghao Yunnan Univ Sch Informat Sci & Engn Kunming Yunnan Peoples R China Yunnan Univ Sch Math & Stat Kunming Yunnan Peoples R China

ISBN: (纸本)9783031221040;9783031221057

In this paper, we study the bound coverage problem by aligned disks in L-1 metric. Suppose U is a set of users, L is a horizontal line on the plane, and S is a set of points on the line L, where each user has a profit. This problem to select a set of disks in L-1 metric such that the center of each disk is a point in S (but with arbitrary radius) and the total profit of the covered users by the selected disk set is at least B, where B is a given profit bound, the disk in L-1 metric is a region with a rotated square boundary, and the relationship between the cost of a disk with radius r is r(alpha) (alpha >= 1). This objective is to minimize the total cost of the selected disks. We prove that this problem is NP-hard even when a = 1, and present a fully polynomial time approximation scheme based on a rounding-and-scaling technique.

关键词： disk coverage problem Bound Fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

The coverage problem by Aligned disks

引用

International Journal of Computational Geometry and Applications 2023年第1-2期33卷 13-23页

作者： Nakano, Shin-Ichi Department of Computer Science Gunma University 1-5-1 Tenjin-Cho Kiryu-Shi 376-8515 Japan

Given a set C of points and a horizontal line L in the plane and a set F of points on L, we want to find a set of disks such that (1) each disk has the center at a point in F (but with arbitrary radius), (2) each point in C is covered by at least one disk, and (3) the cost of the set of disks is minimized. Here the (transmission) cost of a disk with radius r is rα, where α is a positive constant depending on the power consumption model, and the cost of a set of disk is the sum of the cost of disks in the set. In this paper we first give an algorithm based on dynamic programming method to solve the problem in L1 metric. A naive dynamic programming algorithm runs in O(|C|3|F|2) time. We design an algorithm which runs in O(|C||F|2 + |C|log |C|) time. Then we design another algorithm to solve the problem in L1 metric based on a reduction to a shortest path problem in a directed acyclic graph. The running time of the algorithm is O(|C|2 + |C||F|). © 2023 World Scientific Publishing Company.

关键词： Algorithm disk coverage problem

来源：评论

学校读者我要写书评

暂无评论

The coverage problem by Aligned disks 27th

The Coverage Problem by Aligned Disks

引用

27th International Computing and Combinatorics Conference (COCOON)

作者： Nakano, Shin-ichi Gunma Univ Maebashi Gumma Japan

ISBN: (纸本)9783030895433;9783030895426

Given a set C of points and a horizontal line L in the plane and a set F of points on L, we want to find a set of disks such that (1) each disk has the center at a point in F (but with arbitrary radius), (2) each point in C is covered by at least one disk, and (3) the cost of the set of disks is minimized. Here the (transmission) cost of a disk with radius r is ra, where a is a constant depending on the power consumption model, and the cost of a set of disk is the sum of the cost of disks in the set. In this paper we first give an algorithm based on dynamic programming method to solve the problem in L-1 metric. A naive dynamic programming algorithm runs in O(vertical bar C vertical bar(3)vertical bar F vertical bar(2)) time. We design an algorithm which runs in O(vertical bar C vertical bar vertical bar F vertical bar(2)) time. Then we design another algorithm to solve the problem in L-1 metric based on a reduction to a shortest path problem in a directed acyclic graph. The running time of the algorithm is O(vertical bar C vertical bar(2) + vertical bar C vertical bar vertical bar F vertical bar).

关键词： Algorithm disk coverage problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：