An O(nm) algorithm for a special case of the multimedian location problem on a tree

The multimedian location problem on a connected network G is concerned with locating m new facilities on the network. The network G has one existing facility (customer) at each of the n nodes of G. The objective is to locate the new facilities so as to minimize total cost, which is the sum of a) weighted distances between pairs of new and existing facilities and b) weighted distances between certain pairs of new facilities. We show that this problem can be solved in O(nm) when G is a tree and the set of pairs of new facilities which interact has special structure.