The Multimedian Location Problem on a Network Exploiting Block Structure

The multimedian problem is to locate “distinguishable” new facilities on a connected network G so as to minimize a total cost, which is a sum of costs directly proportional to (a) network distances between new facilities and existing facilities at vertex locations and (b) distances between pairs of new facilities. By solving a related multimedian problem in polynomial time on the “blocking graph” of G, which is a tree, we obtain information which localizes each optimal new facility location to some vertex or block (maximal nonseparable subgraph) of G. The problem then decomposes into independent multimedian problems, one for each localizing block, which can be solved by using branch and bound and a vertex-optimality property.