We consider the all-or-nothing multicommodity flow problem in undirected graphs. We are given a capacitated undirected graph and k pairs of vertices. Each pair has a unit demand. The objective is to find a largest subset of these for which we can send a flow of one unit between each pair. This problem is closely related to the classical edge-disjoint path problem (EDP) but differs in that we do not insist on integer flow paths for the pairs. It is also related to several other well studied multicommodity flow problems.
In this talk we describe a poly-logarithmic approximation for the all-or-nothing problem in general undirected graphs. The best previously known approximation was a polynomial ratio, the same as that for EDP. The emphasis will be on connections to related problems includiing the recent work of Racke on oblivious routing.
This is joint work with Sanjeev Khanna and Bruce Shepherd.