Premium
On the p ‐coverage problem on the real line
Author(s) -
Van Hoesel Stan P. M.,
Wagelmans Albert P. M.
Publication year - 2007
Publication title -
statistica neerlandica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.52
H-Index - 39
eISSN - 1467-9574
pISSN - 0039-0402
DOI - 10.1111/j.1467-9574.2007.00347.x
Subject(s) - line (geometry) , mathematics , upper and lower bounds , parametric statistics , real line , mathematical optimization , combinatorics , computer science , statistics , geometry , mathematical analysis
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 log n ) time, n being the number of clients.