Locating facilities which interact: Some solvable cases

Dilip Chhajed, Timothy J. Lowe

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)101-124
Number of pages24
JournalAnnals of Operations Research
Issue number1
StatePublished - Dec 1992
Externally publishedYes

ASJC Scopus subject areas

  • Decision Sciences(all)
  • Management Science and Operations Research


Dive into the research topics of 'Locating facilities which interact: Some solvable cases'. Together they form a unique fingerprint.

Cite this