Improved Bounds on the Max-Flow Min-Cut Ratio for Multicommodity Flows

In this paper we consider the worst case ratio between the capacity of min-cuts and the value of max-flow for multicommodity flow problems. We improve the best known bounds for the mincut max-flow ratio for multicommodity flows in undirected graphs, by replacing the O(log D) in the bound by O(log k), where D denotes the sum of all demands, and k denotes the number of commodities. In essence we prove that up to constant factors the worst min-cut max-flow ratios appear in problems where demands are integral and polynomial in the number of commodities. Klein, Rao, Agrawal, and Ravi have previously proved that if the demands and the capacities are integral, then the min-cut max-flow ratio in general undirected graphs is bounded by O(logC log D), where C denotes the sum of all the capacities. Tragoudas has improved this bound to O(logn log D), where n is the number of nodes in the network. Garg, Vazirani and Yannakakis further improved this to O(log k log D). Klein, Plotkin and Rao have pr..