A note on minimum-sum coverage by aligned disks

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ˆα for any α≥1. The goal is to find a set of disks in any Lp-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⁴logn) time for any α>1 in any Lp-metric. We present a faster algorithm that runs in O(n²logn) time for any α>1 and any Lp-metric.