0
$\begingroup$

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!

2 Answers 2