6.5.5 Multiple CentersBy analogy to the k-medians problem, there is also a k-centers problem. The following definitions are appropriate. Let G(N, A) be an undirected network and let X_{k} = {x_{1}, x_{2}, . . ., X_{k}} be a set of k points on G. We shall use, as before, d(X_{k}, j) = d(x_{i}, j) [i.e., d(X_{k}, j) is the minimum distance between any one of the points x_{i} X_{k} and the node j on G]. Definition: A set of k points X^{*}_{k} on G is a
set of unconstrained (or absolute) k-centers of G. if for
every set X_{k} E G.
Definition: If the sets X_{k}, X^{*}_{k} in Definition 1 are constrained to consist solely of k nodes of the node set N. then the set X^{*}_{k} is a set of vertex k-centers of G. Until recently, k-center problems were believed to be among the most difficult graph problems to solve. The work of Handler [HAND 79] has, however, provided a set of algorithms--which he called "relaxation algorithms"--that solve efficiently problems of considerable size (e.g., n = 200, k= 5). |