科研之友
微信
新浪微博
Facebook
分享链接
摘要
In this paper, we consider a facility location problem to find a minimum-sum coverage of n points by disks centered at a fixed line. The cost of a disk with radius r has the form of a nondecreasing function f (r) = r(alpha) for any alpha >= 1. The goal is to find a set of disks in any L-p-metric such that the disks are centered on the x-axis, their union covers the points, and the sum of the cost of the disks is minimized. Alt et al. [1] presented an algorithm running in O (n(4) log n) time for any alpha >1 in any L-p-metric. We present a faster algorithm that runs in O(n(2) log n) time for any alpha > 1 and any L-p-metric.
- 出版日期2013-12
