The unsplittable flow problem is a variant of the normal ("fractional")
flow problem where the flow from the source to any terminal must all be
along a single path. It combines two fundamental network problems:
routing (finding good paths for network traffic), and packing
(combining multiple paths in a single network while respecting capacity
constraints). As a generalization of both the disjoint paths problem
and bin packing, it is NP-complete. Until recently, no good
approximation algorithms for unsplittable flow problems were known.
In this talk, we will describe recent work by Jon Kleinberg (presented
at FOCS 96) which provides constant-factor approximations for several
single-source multiple-sink unsplittable flow problems. We will also
consider some generalizations to the multiple source case.