Tech Report CS-91-17

An Approximate Max-flow Min-cut Relation for Multicommodity Flow and its Applications

Philip Klein, Ajit Agrawal, R. Ravi and Satish Rao

March 1991

Abstract:

In this paper, we prove the first approximate max-flow min-cut theorem for general multicommodity flow. We show that for a feasible flow to exist in a multicommodity problem, it is sufficient that every cut's capacity exceeds its demand by a factor of $\mbox{O}(\log C \log D)$, where $C$ is the sum of edge capacities and $D$ is the sum of demands. Moreover, our theorem yields an algorithm for finding a cut that is approximately minimum {\it relative} to the flow that must cross it. We use this result to obtain approximation algorithms for minimum deletion of clauses of a 2-CNF$\equiv$ formula, via minimization, and other problems.

(complete text in pdf)