An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
Authors:
- Yonatan AumannYAYonatan Aumann
- Yuval RabaniYRYuval Rabani
- 1 February 1998
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 27 (1) , 291-301
Abstract
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.Keywords
This publication has 23 references indexed in Scilit:
- The geometry of graphs and some of its algorithmic applicationsCombinatorica, 1995
- Fast Approximation Algorithms for Multicommodity Flow ProblemsJournal of Computer and System Sciences, 1995
- The cut cone, L1 embeddability, complexity, and multicommodity flowsNetworks, 1991
- PrefaceDiscrete Applied Mathematics, 1985
- On lipschitz embedding of finite metric spaces in Hilbert spaceIsrael Journal of Mathematics, 1985
- Decomposition of Km,n(Km,n∗) into cycles (circuits) of length 2kJournal of Combinatorial Theory, Series B, 1981
- On Two Commodity Network FlowsOperations Research, 1966
- Multi-Commodity Network FlowsOperations Research, 1963
- A note on the maximum flow through a networkIEEE Transactions on Information Theory, 1956
- Maximal Flow Through a NetworkCanadian Journal of Mathematics, 1956