A heuristic for the p-center problem in graphs (Q1098862)

The author gives an algorithm of \(O(n^ 2\log n)\) running time with a worst-case error ratio of 2 for the p-centerproblem in a connected graph of n nodes and m edges with edge lengths and vertex weights. A slight modification of the algorithm provides a ratio 2 also for the absolute p- center problem with running time \(O(mn^ 2\log n)\). Both heuristics are best possible.