Journal article
An O(nm) algorithm for a special case of the multimedian location problem on a tree
European journal of operational research, Vol.63(2), pp.222-230
12/10/1992
DOI: 10.1016/0377-2217(92)90027-7
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. 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.
Details
- Title: Subtitle
- An O(nm) algorithm for a special case of the multimedian location problem on a tree
- Creators
- Dilip Chhajed - University of Illinois Urbana-ChampaignTimothy J. Lowe - University of Iowa
- Resource Type
- Journal article
- Publication Details
- European journal of operational research, Vol.63(2), pp.222-230
- DOI
- 10.1016/0377-2217(92)90027-7
- ISSN
- 0377-2217
- eISSN
- 1872-6860
- Publisher
- Elsevier B.V
- Number of pages
- 9
- Language
- English
- Date published
- 12/10/1992
- Academic Unit
- Business Analytics
- Record Identifier
- 9984963207102771
Metrics
1 Record Views