Designing multi-commodity flow trees

Samir Khuller*, Balaji Raghavachari, Neal Young

*Corresponding author for this work

Research output: Contribution to journalArticle

13 Scopus citations

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(log2n) approximation factor obtained by a direct application of the balanced-separator method.

Original languageEnglish (US)
Pages (from-to)49-55
Number of pages7
JournalInformation Processing Letters
Volume50
Issue number1
DOIs
StatePublished - Apr 8 1994

Keywords

  • Analysis of algorithms
  • Combinatorial problems
  • Congestion
  • Network design
  • Network flow

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Designing multi-commodity flow trees'. Together they form a unique fingerprint.

  • Cite this