TY - GEN

T1 - Approximation algorithms for the unsplittable flow problem

AU - Chakrabarti, Amit

AU - Chekuri, Chandra

AU - Gupta, Anuptam

AU - Kumar, Amit

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.

PY - 2002

Y1 - 2002

N2 - 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].

AB - 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].

UR - http://www.scopus.com/inward/record.url?scp=84957021733&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84957021733&partnerID=8YFLogxK

U2 - 10.1007/3-540-45753-4_7

DO - 10.1007/3-540-45753-4_7

M3 - Conference contribution

AN - SCOPUS:84957021733

SN - 3540441867

SN - 9783540441861

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 51

EP - 67

BT - Approximation Algorithms for Combinatorial Optimization - 5th International Workshop, APPROX 2002, Proceedings

A2 - Jansen, Klaus

A2 - Leonardi, Stefano

A2 - Vazirani, Vijay

PB - Springer-Verlag Berlin Heidelberg

T2 - 5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002

Y2 - 17 September 2002 through 21 September 2002

ER -