The multi-service center problem

In this paper, we show that the p-service center problem on a general graph is NP-hard, and propose a simple approximation algorithm of factor p/c for any integer constant c. Moreover, we study the basic case p=2 on paths and trees. When the underlying network is a path, we solve the 2-service center problem in O(n) time, where n is the number of vertices. When the underlying network is a tree, we give an O(n3)-time algorithm for the case of nonnegative weights, an O(nlog⁡n)-time algorithm for the case of positive weights, and an O(n)-time algorithm for the case of uniform weights.