Approximation algorithms for the unsplittable flow problem

Amit Chakrabarti, Chandra Chekuri, Anuptam Gupta, Amit Kumar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present approximation algorithms for the unsplittable flow problem (UFP) on 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: – For undirected graphs we obtain a O(Δα−1 log2n) approximation ratio, where n is the number of vertices, Δ the maximum degree, and α the expansion of the graph. Our ratio is capacity independent and improves upon the earlier O(Δα1(cmax/cmin) log n) bound [15] for large values of cmax/cmin. Furthermore, if we specialize to the case where all edges have the same capacity, our algorithm gives an O(Δα1 log n) approximation, which matches the performance of the best-known algorithm [15] for this special case. – For certain strong constant-degree expanders considered by Frieze [10] we obtain an O(√log n) approximation for the uniform capacity case, improving upon the current O(log n) approximation. – For UFP on the line and the ring, we give the first constant-factor approximation algorithms. Previous results addressed only the uniform capacity case. – All of the above results improve if the maximum demand is bounded away from the minimum capacity. Our results are based on randomized rounding followed by greedy alteration and are inspired by the use of this idea in recent work [21, 9].

Original languageEnglish (US)
Title of host publicationApproximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings
EditorsKlaus Jansen, Stefano Leonardi, Vijay Vazirani
PublisherSpringer-Verlag Berlin Heidelberg
Pages51-67
Number of pages17
ISBN (Print)3540441867, 9783540441861
DOIs
StatePublished - 2002
Externally publishedYes
Event5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002 - Rome, Italy
Duration: Sep 17 2002Sep 21 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2462
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002
CountryItaly
CityRome
Period9/17/029/21/02

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this