Show simple item record

Designing Multi-Commodity Flow Trees

dc.contributor.authorKhuller, Samiren_US
dc.contributor.authorRaghavachari, Balajien_US
dc.contributor.authorYoung, Nealen_US
dc.description.abstractThe 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.extent185740 bytes
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3042en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-93-20en_US
dc.titleDesigning Multi-Commodity Flow Treesen_US
dc.typeTechnical Reporten_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record