In this paper, we study the K-prize-collecting coverageproblem 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 corres...
详细信息
In this paper, we study the K-prize-collecting coverageproblem 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.
In this paper, we study the K $K$ -prize-collecting coverageproblem 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$ , w...
详细信息
In this paper, we study the K $K$ -prize-collecting coverageproblem 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.
In this paper, we study the bound coverageproblem 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...
详细信息
ISBN:
(纸本)9783031221040;9783031221057
In this paper, we study the bound coverageproblem 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.
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 poin...
详细信息
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 poin...
详细信息
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).
暂无评论