The flow/cut gap theorem for multicommodity flow

Question

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!

Answer 1

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

Answer 2

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.