In traditional multi-commodity flow theory, the task is to send a
certain amount of each commodity from its start to its target node,
subject to capacity constraints on the edges. However, no
restriction is imposed on the number of paths used for delivering
each commodity; it is thus feasible to spread the flow over a large
number of different paths. Motivated by routing problems arising in
real-life applications, such as, e.g., telecommunication,
unsplittable flows have moved into the focus of research. Here, the
demand of each commodity may not be split but has to be sent along a
single path.
In this paper, a generalization of this problem is studied. In the
considered flow model, a commodity can be split into a bounded
number of chunks which can then be routed on different paths. In
contrast to classical (splittable) flows and unsplittable flows,
already the single-commodity case of this problem is NP-hard and
even hard to approximate. We present approximation algorithms for
the single- and multi-commodity case and point out strong
connections to unsplittable flows. Moreover, results on the
hardness of approximation are presented. It particular, we show
that some of our approximation results are in fact best possible,
unless P=NP.
