An O (log k ) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
Yonatan Aumann, Yuval Rabani · SIAM Journal on Computing · 1998
It is shown that the minimum cut ratio is within a factor of O(log k) of the maximum concurrent flow for k-commodity flow instances with arbitrary capacities and demands. This improves upon the previously best-known bound of O(log 2 k ) and is existentially tight, up to a constant factor. An algorithm for finding a cut with ratio within a factor of O(log k) of the maximum concurrent flow, and thus of the optimal min-cut ratio, is presented.