کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427133 | 686455 | 2013 | 5 صفحه PDF | دانلود رایگان |
• We consider a minimum-sum coverage problem by disks aligned on a fixed line.
• The goal is to minimize the sum of radius rαrα for disks for some real α⩾1α⩾1.
• We present an algorithm running in O(n2logn) time for any LpLp-metric.
• The best known previous algorithm runs in O(n4logn) time.
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αf(r)=rα for any α⩾1α⩾1. The goal is to find a set of disks in any LpLp-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(n4logn) time for any α>1α>1 in any LpLp-metric. We present a faster algorithm that runs in O(n2logn) time for any α>1α>1 and any LpLp-metric.
Journal: Information Processing Letters - Volume 113, Issues 22–24, November–December 2013, Pages 871–875