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