hide
Free keywords:
-
Abstract:
In classical network flow theory, flow being sent from a source to a
destination may be split into a large number of chunks traveling on different
paths through the network. This effect is undesired or even forbidden in many
applications. Kleinberg introduced the unsplittable flow problem where all flow
traveling from a source to a destination must be sent on only one path. This is
a generalization of the NP-complete edge-disjoint paths problem. In particular,
the randomized rounding technique of Raghavan and Thompson can be applied. A
generalization of unsplittable flows are k-splittable flows where the number of
paths used by a commodity $i$ is bounded by a given integer~$k_i$.
The contribution of this paper is twofold. First, for the unsplittable flow
problem, we prove a lower bound of~$\Omega(\log m/\log\log m)$ on the
performance of randomized rounding. This result matches the best known upper
bound of~$O(\log m/\log\log m)$. To the best of our knowledge, the problem of
finding a non-trivial lower bound has so far been open.
In the second part of the paper, we study a new variant of the k-splittable
flow problem with additional constraints on the amount of flow being sent along
each path. The motivation for these constraints comes from the following
packing and routing problem: A commodity must be shipped using a given number
of containers of given sizes. First, one has to make a decision on the fraction
of the commodity packed into each container. Then, the containers must be
routed through a network whose edges correspond, for example, to ships or
trains. Each edge has a capacity bounding the total size or weight of
containers which are being routed on it. We present approximation results for
two versions of this problem with multiple commodities and the objective to
minimize the congestion of the network. The key idea is to reduce the problem
under consideration to an unsplittable flow problem while only losing a
constant factor in the performance ratio.
