On the p-coverage problem on the real line

On the p-coverage problem on the real line

0.00 Avg rating0 Votes
Article ID: iaor20072767
Country: Netherlands
Volume: 61
Issue: 1
Start Page Number: 16
End Page Number: 34
Publication Date: Feb 2007
Journal: Statistica Neerlandica
Authors: ,
Keywords: p-median problem
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.