Approximate Max-Flow Min-Cut Theorem for Uniform Multicommodity Flow Problems with Applications to Approximation Algorithms.

摘要

In this paper, we consider a multicommodity flow problem where for each pair of vertices, (u.v), we are required to send f half-units of commodity (u,v) from u to v and f half-units of commodity (u,v) for v to u without violating capacity constraints. Our main result is an algorithm for performing the task provided that the capacity of each cut exceeds the demand across the cut by a theta(log n) factor. The condition on cuts is required in the worst case, and is trivially within a theta(log n) factor of optimal for any flow problem. The result is of interest because it can be used to construct the first poly-log times optimal approximation algorithms for a wide variety of problems, including minimum quotient separators, 1/3-2/3 separators, bifurcators, crossing number and VLSI layout area. The result can also be used to efficiently route packets in arbitrary distributed networks. For example, we can prove that any n-node bounded degree graph, G, with minimum edge expansion alpha can be configured off-line to simulate any n-node bounded degree graph H in )(log n/alpha) steps using constant size queues. (kr)