Approximation Algorithms for the Unsplittable Flow Problem

We give an O(D/a log n)-approximation algorithm for the Uniform Capacity Unsplittable Flow Problem (UCUFP) with weights, on an expander with degree D and expansion a. We also give an O(D/a log^2 n)-approximation algorithm for the more general Unsplittable Flow Problem (UFP), with the maximum demand at most the minimum edge capacity, on such expanders. 

We establish these results by showing the existence of a near optimal solution to the multicommodity flow relaxation for UFP that uses only short paths, in particular paths of length O(D/a log n). This observation is based on a procedure to shortcut long paths adapted from papers by Kleinberg and Rubinfeld, and more recently Kolman and Scheideler and improves the previous bound of O(D/a log^3 n) on the flow paths lengths shown in. 

For strong regular expanders on which any O(n/log n) pairs can be connected by disjoint paths, we obtain an improved approximation for UCUFP. The above results improve if the maximum demand is bounded away from the minimum capacity. For UFP on the line we give an O(1) factor approximation when the maximum demand is smaller than the minimum capacity. Alternatively, we obtain an O(1) approximation without the restriction, provided that we are allowed.