Locating facilities which interact: Some solvable cases

The network version of the m-median problem with mutual communication (MMMC) is to find the location of m new facilities on a network with n nodes such that the sum of (a) the cost of interaction between the new facilities and n existing facilities on the network, and (b) the cost of interaction between pairs of new facilities is minimized. The existing facilities are located at nodes of the network and the interaction cost between a pair of facilities is a function of the network distance between the facilities. This problem is shown to be equivalent to a graph-theoretic Node Selection Problem (NSP). We show that many other problems can be formulated as an NSP. We then provide a polynomial time algorithm to solve NSP for the case when the flow graph is Halin. Extensions to other graph families are provided.