neal young / Khuller94Designing

Information Processing Letters 50(1):4955(1994); WADS'93The traditional multicommodity 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 multicommodity flow networkdesign problem: given a set of multicommodity 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 minimumweight balancedseparator problem; the performance guarantee of the algorithm is within a factor of 4 of the performance guarantee of the balancedseparator procedure. If Tom Leighton and Satish Rao's balancedseparator procedure [1988] is used, the performance guarantee is $O(\log n)$. This improves the $O(\log^2 n)$ approximation factor that is trivial to obtain by a direct application of the balancedseparator method.Journal version of [1993].
© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.