Approximate Max-Flow Min- (Multi) Cut Theorems and their Applications

Consider multicommodity flow problem in which the object is to maximize the sum of commodities routed. We prove the following approximate max-flow min-multicut theorem: min multicut over O(log k)