A Comparison of the Effectiveness of Two Novel Clustering-Based Heuristics for the p-Centre Problem

Given a set of n demand points, the objective of the p-centre problem is to identify a subset of the demand points having p ≪ n nodes (called centres) such that the maximum distance of any demand point to its nearest centre is minimized. The problem is NP-hard and finds application in facility location. This paper presents two novel heuristics for the p-centre problem that requires O(n3) time. One of these is a deterministic heuristic that uses a minimum spanning tree-based clustering approach, and the other is a randomized heuristic that uses greedy clustering. Bounds on the computational time requirements of both heuristics are proved. The relative performance of the two heuristics is evaluated in the course of several computational experiments on a wide range of benchmark problems used in the literature for the p-centre problem.