The fractional congestion bound for efficient edge disjoint routing

This article investigates the following problem: Given the fractional relaxation of the edge disjoint routing problem, how small a fractional congestion is sufficient to guarantee efficient edge disjoint routing? That is, what is the largest possible value v such that a fractional flow with congestion at most v , can be efficiently converted into an edge disjoint routing? Leighton, Lu, Rao, and Srinivasan (SIAM J Comput 2001) have established that fractional congestion of at most the order of O (1/( d log k )) is sufficient, where d is the maximum path length in the fractional relaxation, and k is the number of pairs to be routed. It is also known that Θ (1/ d ) is the correct bound, if we are only interested in an existence result (Leighton, Rao, and Srinivasan, Hawaii International Conference on System Sciences, 1998). Motivated by the fact that d is small for many types of routing problems, specifically, polylogarithmic for expander graphs, this article improves upon the former result by showing O (1/( d log d )) fractional congestion to suffice. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008