An <i>O</i>(log <i>k</i>) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm 论文
1998SIAM Journal on Computing引用 264
Complexity and Algorithms in GraphsOptimization and Search ProblemsAdvanced Graph Theory Research
详细信息
- 发表期刊/会议
- SIAM Journal on Computing
- 发表日期
- 1998-02-01
- 发表年份
- 1998
关键词
Complexity and Algorithms in GraphsOptimization and Search ProblemsAdvanced Graph Theory Research
摘要
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(log2k ) 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.