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

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

0.00 Avg rating0 Votes
Article ID: iaor1996748
Country: Netherlands
Volume: 63
Issue: 2
Start Page Number: 222
End Page Number: 230
Publication Date: Dec 1992
Journal: European Journal of Operational Research
Authors: ,
Keywords: facilities
Abstract:

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. The authors 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.

Reviews

Required fields are marked *. Your email address will not be published.