This means that the multi-cut is at most away from the optimal value for the max multi-cut commodity flow problem for a factor O(log k).
| From here
we draw the conclusion that the ratio the capacity of the edges on the border
of the ball is at most 2 log 2 k the volume of the ball and then
that we can implement this procedure achieving a O(log k)
approximation. This means that the multi-cut is at most away from the optimal value for the max multi-cut commodity flow problem for a factor O(log k). |
|
