The Multimedian Location Problem on a Network Exploiting Block Structure

Y. Xu, Richard L. Francis and Timothy J. Lowe
Additional contact information
Y. Xu: Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611
Richard L. Francis: Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611
Timothy J. Lowe: Department of Management Sciences, University of Iowa, Iowa City, Iowa 52242

Transportation Science, 1994, vol. 28, issue 2, 116-124

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.

Date: 1994
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.28.2.116 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:28:y:1994:i:2:p:116-124

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().