Approximation algorithms for the unsplittable flow problem

Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, Amit Kumar

Research output: Contribution to journalArticlepeer-review

Abstract

We present approximation algorithms for the unsplittable flow problem (UFP) in undirected graphs. As is standard in this line of research, we assume that the maximum demand is at most the minimum capacity. We focus on the non-uniform capacity case in which the edge capacities can vary arbitrarily over the graph. Our results are: We obtain an O(Δα -1 log 2 n) approximation ratio for UFP, where n is the number of vertices, Δ is the maximum degree, and α is the expansion of the graph. Furthermore, if we specialize to the case where all edges have the same capacity, our algorithm gives an O(Δα -1 log n) approximation. For certain strong constant-degree expanders considered by Frieze [17] we obtain an O(√log n) approximation for the uniform capacity case. For UFP on the line and the ring, we give the first constant-factor approximation algorithms. All of the above results improve if the maximum demand is bounded away from the minimum capacity. The above results either improve upon or are incomparable with previously known results for these problems. The main technique used for these results is randomized rounding followed by greedy alteration, and is inspired by the use of this idea in recent work.

Original languageEnglish (US)
Pages (from-to)53-78
Number of pages26
JournalAlgorithmica (New York)
Volume47
Issue number1
DOIs
StatePublished - Jan 2007

Keywords

  • Alteration
  • Approximation algorithms
  • Disjoint paths
  • Expanders
  • Line networks
  • Randomized rounding
  • Ring network
  • Unsplittable flow problem

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Approximation algorithms for the unsplittable flow problem'. Together they form a unique fingerprint.

Cite this