Designing Multi-Commodity Flow Trees
| dc.contributor.author | Khuller, Samir | en_US |
| dc.contributor.author | Raghavachari, Balaji | en_US |
| dc.contributor.author | Young, Neal | en_US |
| dc.date.accessioned | 2004-05-31T22:23:09Z | |
| dc.date.available | 2004-05-31T22:23:09Z | |
| dc.date.created | 1993-03 | en_US |
| dc.date.issued | 1998-10-15 | en_US |
| dc.description.abstract | The traditional multi-commodity flow problem assumes a given flow network in which multiple commodities are to be maximally routed in response to given demands.This paper considers the multi-commodity flow network-design problem: given a set of multi-commodity flow demands, find a network subject to certain constraints such that the commodities can be maximally routed. This paper focuses on the case when the network is required to be a tree. The main result is an approximation algorithm for the case when the tree is required to be of constant degree. The algorithm reduces the problem to the minimum-weight balanced-separator problem; the performance guarantee of the algorithm is within a factor of 4 of the performance guarantee of the balanced-separator procedure. If Leighton and Rao's balanced-separator procedure is used, the performance guarantee is O(\log n). This improves the O(\log^2 n) approximation factor obtained by a direct application of the balanced-separator method. (Also cross-referenced as UMIACS-TR-93-20) | en_US |
| dc.format.extent | 185740 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/582 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-3042 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-93-20 | en_US |
| dc.title | Designing Multi-Commodity Flow Trees | en_US |
| dc.type | Technical Report | en_US |