Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Thanks!

share|improve this question
add comment

2 Answers 2

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.)

share|improve this answer
    
Thanks, this is really great set of lectures –  com Dec 11 '11 at 20:31
add comment

http://www.seas.upenn.edu/~deepc/Courses/CIS800/Notes/lec8.pdf

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.

share|improve this answer
    
thanks, I very appreciate it! –  com Dec 21 '11 at 12:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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