TY - GEN
T1 - Strongly polynomial algorithms for the unsplittable flow problem
AU - Azar, Yossi
AU - Regev, Oded
PY - 2001
Y1 - 2001
N2 - We provide the first strongly polynomial algorithms with the best approximation ratio for all three variants of the unsplittable flow problem (UFP). In this problem we are given a (possibly directed) capacitated graph with n vertices and m edges, and a set of terminal pairs each with its own demand and profit. The objective is to connect a subset of the terminal pairs each by a single flow path as to maximize the total profit of the satisfied terminal pairs subject to the capacity constraints. Classical UFP, in which demands must be lower than edge capacities, is known to have an O(√m) approximation algorithm. We provide the same result with a strongly polynomial combinatorial algorithm. The extended UFP case is when some demands might be higher than edge capacities. For that case we both improve the current best approximation ratio and use strongly polynomial algorithms. We also use a lower bound to show that the extended case is provably harder than the classical case. The last variant is the bounded UFP where demands are at most K of the minimum edge capacity. Using strongly polynomial algorithms here as well, we improve the currently best known algorithms. Specifically, for K = 2 our results are better than the lower bound for classical UFP thereby separating the two problems.
AB - We provide the first strongly polynomial algorithms with the best approximation ratio for all three variants of the unsplittable flow problem (UFP). In this problem we are given a (possibly directed) capacitated graph with n vertices and m edges, and a set of terminal pairs each with its own demand and profit. The objective is to connect a subset of the terminal pairs each by a single flow path as to maximize the total profit of the satisfied terminal pairs subject to the capacity constraints. Classical UFP, in which demands must be lower than edge capacities, is known to have an O(√m) approximation algorithm. We provide the same result with a strongly polynomial combinatorial algorithm. The extended UFP case is when some demands might be higher than edge capacities. For that case we both improve the current best approximation ratio and use strongly polynomial algorithms. We also use a lower bound to show that the extended case is provably harder than the classical case. The last variant is the bounded UFP where demands are at most K of the minimum edge capacity. Using strongly polynomial algorithms here as well, we improve the currently best known algorithms. Specifically, for K = 2 our results are better than the lower bound for classical UFP thereby separating the two problems.
UR - http://www.scopus.com/inward/record.url?scp=84947291208&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84947291208&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84947291208
SN - 3540422250
SN - 9783540422259
VL - 2081
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 15
EP - 29
BT - Integer Programming and Combinatorial Optimization - 8th International IPCO Conference, Proceedings
PB - Springer Verlag
T2 - 8th International Integer Programming and Combinatorial Optimization Conference, IPCO 2001
Y2 - 13 June 2001 through 15 June 2001
ER -