Journal article
The Multimedian Location Problem on a Network Exploiting Block Structure
Transportation science, Vol.28(2), pp.116-124
05/1994
DOI: 10.1287/trsc.28.2.116
Abstract
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.
Details
- Title: Subtitle
- The Multimedian Location Problem on a Network Exploiting Block Structure
- Creators
- Y. Xu - University of FloridaRichard L. Francis - University of FloridaTimothy J. Lowe - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Transportation science, Vol.28(2), pp.116-124
- DOI
- 10.1287/trsc.28.2.116
- ISSN
- 0041-1655
- eISSN
- 1526-5447
- Number of pages
- 9
- Language
- English
- Date published
- 05/1994
- Academic Unit
- Business Analytics
- Record Identifier
- 9984963192702771
Metrics
1 Record Views