Abstract
In this paper we consider the unsplittable flow problem (UFP): given a network $G=(V,E)$ with edge capacities and a set of terminal pairs (or requests) with associated demands, find a subset of the pairs of maximum total demand for which a single flow path can be chosen for each pair so that for every edge, the sum of the demands of the paths crossing the edge does not exceed its capacity. We present a collection of new results for the UFP both in the offline and the online setting.
A fundamental ingredient of our analysis is the introduction of a new graph parameter, the flow number, that aims to capture global communication properties of the network. With the help of the flow number we develop a general method for transforming arbitrary multicommodity flow solutions into solutions that use short paths only.
This generalizes a well-known theorem of Leighton and Rao that applies to uniform flows only. Both the parameter and the method may therefore be of independent interest.