Approximation Algorithms for Single-Source Unsplittable Flow

Abstract

In the single-source unsplittable flow problem, we are given a network G, a source vertex s, and k commodities with sinks ti and real-valued demands $\rho_i,$ $1\leq i \leq k.$ We seek to route the demand $\rho_i$ of each commodity i along a single s-ti flow path so that the total flow routed across any edge e is bounded by the edge capacity ue. The conceptual difficulty of this NP-hard problem arises from combining packing constraints due to the existence of capacities with path selection in a graph of arbitrary topology. In this paper we give a generic framework, which yields approximation algorithms that are simpler than those previously known and achieve significant improvements upon the approximation ratios. Our framework, with appropriate subroutines, applies to all optimization versions previously considered and, unlike previous work, treats in a unified manner directed and undirected graphs. We provide extensions of our algorithms which yield the best possible approximation guarantees for restricted sets of demand values and an associated scheduling problem.