Tel-Aviv University - Computer Science Colloquium
Sunday, May 14, 14:15-15:15
at 14:00
Schreiber Building, Room 309
Strongly Polynomial Algorithms
for the Unsplittable Flow Problem
Oded Regev
Computer Science Department, Tel Aviv University
Abstract:
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(\sqrt 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 1/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.
This is joint work with Yossi Azar
For colloquium schedule, see
http://www.math.tau.ac.il/~zwick/colloq.html