DIMACS TR: 93-78

On reducing the cut ratio to the multicut problem



Author: Nabil Kahale

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 $\alpha$, for any subset of commodities, then the minimum cut ratio is approximated by the maximum concurrent flow within a factor of $O(\alpha\ln k)$.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-78.ps
DIMACS Home Page