ON A GENERALIZATION OF THE P-CENTER PROBLEM

We study a generalization of the p-Center Problem, which we call the alpha-Neighbor p-Center Problem (p-CENTER(alpha)). Given a complete edge-weighted network, the goal is to minimize the maximum distance of a client to its a nearest neighbors in the set of p centers. We show that in general finding a O(2(poly)(\V\))-approximation for p-CENTER(alpha) is NP-hard, where \V\ denotes the number of nodes in the network. If the distances are required to satisfy the triangle inequality, there can be no polynomial time approximation algorithm with a (2 - epsilon) performance guarantee for any fixed epsilon > O and any fixed alpha less than or equal to p, unless P = NP. For this case, we present a simple yet efficient algorithm that provides a 4-approximation for alpha greater than or equal to 2. If alpha = 1, our algorithm basically falls back to the algorithm presented in [2] and has a relative performance guarantee of 2.