loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
37th Annual Symposium on Foundations of Computer Science (FOCS '96)
Single-source unsplittable flow
Burlington, VT
October 14-October 16
ISBN: 0-8186-7594-2
J.M. Kleinberg, Lab. for Comput. Sci., MIT, Cambridge, MA, USA
The max-flow min-cut theorem of Ford and Fulkerson is based on an even more foundational result, namely Menger's theorem on graph connectivity Menger's theorem provides a good characterization for the following single-source disjoint paths problem: given a graph G, with a source vertex s and terminals t1,...,tk, decide whether there exist edge-disjoint s-ti paths for i=1,...,k.We consider a natural, NP-hard generalization of this problem, which we call the single-source unsplittable flow problem. We are given a source and terminals as before; but now each terminal ti has a demand pi ≤ 1, and each edge e of G has a capacity ce ≥ 1. The problem is to decide whether one can choose a single s-ti path for each i, so that the resulting set of paths respects the capacity constraints-the total amount of demand routed across any edge e must be bounded by the capacity ce. The main results of this paper are constant-factor approximation algorithms for three natural optimization versions of this problem, in arbitrary directed and undirected graphs. The development of these algorithms requires a number of new techniques for rounding fractional solutions to network flow problems; for two of the three problems we consider, there were no previous techniques capable of providing an approximation in the general case, and for the third, the randomized rounding algorithm of Raghavan and Thompson provides a logarithmic approximation. Our techniques are also of interest from the perspective of a family of NP-hard load balancing and machine scheduling problems that can be reduced to the single-source unsplittable flow problem.
Index Terms:
scheduling; unsplittable flow; max-flow min-cut; NP-hard; generalization; load balancing; machine scheduling; capacity constraints
Citation:
J.M. Kleinberg, "Single-source unsplittable flow," focs, pp.68, 37th Annual Symposium on Foundations of Computer Science (FOCS '96), 1996
Usage of this product signifies your acceptance of the Terms of Use.