On the p‐coverage problem on the real line
On the p‐coverage problem on the real line
复制标题
关于实线上的p覆盖问题
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
A. Wagelmans
中科院分区：
文献类型：
--
作者：
Stan van Hoesel;A. Wagelmans
本文研究了实线上的p‐覆盖问题。我们首先详细描述了一种求解开放设施数量不上界p的覆盖问题的算法。然后，我们分析了当所有设施的设置成本都降低相同数量时，最优解的结构是如何变化的。该结果用于开发p -覆盖问题的参数化方法，该问题在O （pn logn）时间内运行，n为客户端数量。
In this paper we consider the p‐coverage problem on the real line. We first give a detailed description of an algorithm to solve the coverage problem without the upper bound p on the number of open facilities. Then we analyze how the structure of the optimal solution changes if the setup costs of the facilities are all decreased by the same amount. This result is used to develop a parametric approach to the p‐coverage problem which runs in O (pn logn) time, n being the number of clients.