On reducing the cut ratio to the multicut problem.

Content Provider	CiteSeerX
Abstract	We compare two multicommodity flow problems, the maximum sum of flow, and the maximum concurrent flow. We show that, for a given graph and a given set of k commodities with specified demands, if the minimum capacity of a multicut is approximated by the maximum sum of flow within a factor of ff, for any subset of commodities, then the minimum cut ratio is approximated by the maximum concurrent flow within a factor of O(ff ln k). 1 Introduction Throughout this note, we are given an undirected graph G = (V; E) where each edge e is assigned a nonnegative real number c(e), called capacity of e . A flow from a vertex s called source to a vertex t called sink is a function ff from the set of paths P(s; t) from s to t into the set of nonnegative real numbers. The value of the flow ff is P P2P(s;t) ff(P ). In a multicommodity flow problem, we are given a set Q of k commodities. A commodity i is specified by a pair of source and sink (s i ; t i ). A flow in this case is a function ff that as...
File Format	PDF
Access Restriction	Open
Subject Keyword	Cut Ratio Multicut Problem Maximum Sum Function Ff Nonnegative Real Number Maximum Concurrent Flow Multicommodity Flow Problem Minimum Capacity Ff Ln Minimum Cut Ratio Specified Demand Flow Ff Undirected Graph
Content Type	Text