THE P-NEIGHBOR K-CENTER PROBLEM

The k-center problem with triangle inequality is that of placing k cen ter nodes in a weighted undirected graph in which the edge weights obe y the triangle inequality, so that the maximum distance of any node to its nearest center is minimized. In this paper, we consider a general ization of this problem where, given a number p, we wish to place k ce nters so as to minimize the maximum distance of any non-center node to its pth closest center. We derive a best possible approximation algor ithm for this problem. (C) 1998 Elsevier Science B.V.