P-Coverage Problem on the Real Line

摘要

The p-coverage problem on the real line is considered. A detailed description ofan algorithm to solve the coverage problem without the upper bound p on the number of open facilities is given. The change in the structure of the optimal solution when the setup costs of the facilities are all decreased by the same amount is analyzed. This result is used to develop a parametric approach to the p-coverage problem which runs in O(pnlogn) time, n being the number of clients.