New Algorithms for Facility Location Problems on the Real Line

作者：Chen Danny Z; Wang Haitao^*

来源：Algorithmica, 2014, 69(2): 370-383.

DOI：10.1007/s00453-012-9737-0

• Facility location
• Real line
• k-median
• k-coverage
• Algorithm design and analysis

In this paper, we study the facility location problems on the real line. Given a set of n customers on the real line, each customer having a cost for setting up a facility at its position, and an integer k, we seek to find at most k of the customers to set up facilities for serving all n customers such that the total cost for facility set-up and service transportation is minimized. We consider several problem variations including the k-median, the k-coverage, and the linear model. The previously best algorithms for these problems all take O(nk) time. Our new algorithms break the O(nk) time bottleneck and solve these problems in sub-quadratic time. Our algorithms are based on a new problem modeling and interesting algorithmic techniques, which may find other applications as well.

• 出版日期2014-6