Let's start out by reviewing very popular max-flow min-cut theorem

Max-flow min-cut theorem:

The maximum value of an $s-t$ flow is equal to the minimum capacity of an $s-t$ cut.

For details: Max-flow min-cut theorem on Wikipedia

The next step is to consider multicommodity flow and multicut.

Multi-commodity flow problem on Wikipedia

Multicut is a relaxation of the dual linear problem to multicommodoty flow. It's well know that multicut problem is NP-hard, therefore can be solved approximately.

The flow/cut gap (integrality gap) theorem:

minimum multicut $\leq O(logk)$ * maximum multicommodity-flow

The problem is I am looking for the proof of this theorem. I found just one pretty descriptive but for me a little bit complicated proof on very advanced level in the book of Vazirani "Approximation Algorithms". 20. Multicut in General Graphs. Page 186. I will appreciate if you have any other proof just in order to make a broad picture.



May I recommend you these lectures of Anupam Gupta?

Lecture 19: Sparsest Cut

Lecture 20: Embeddings into Trees and L1 Embeddings

The first one will guide you through understanding the relation of sparsest cut approximations and metric embeddings, and the second will give you an idea on how to embed arbitrary finite metric spaces into $l_1$ with low distortion. (Note that I only read the first one, and found it quite approachable.)

  • $\begingroup$ Thanks, this is really great set of lectures $\endgroup$ – com Dec 11 '11 at 20:31


look at ckr algo for finding a multi-cut. Theorem 2 state that this cut is no bigger then logn from min fractional cut which is equal to the max flow.

  • $\begingroup$ thanks, I very appreciate it! $\endgroup$ – com Dec 21 '11 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.