## 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