An O(log k) approximate min-cut max-flow theorem and approximation algorithm

被引：153
作者：
Aumann, Y [1 ]
Rabani, Y
机构：
[1] Bar Ilan Univ, Dept Comp Sci, IL-52900 Ramat Gan, Israel
[2] MIT, Comp Sci Lab, Cambridge, MA 02139 USA
[3] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel
来源：
SIAM JOURNAL ON COMPUTING | 1998年 / 27卷 / 01期
关键词：
approximation algorithms; cuts; sparse cuts; network flow; multicommodity flow;
D O I：
10.1137/S0097539794285983
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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.
引用
收藏
页码：291 / 301
页数：11
相关论文
共 35 条
  • [1] ADELSONWELSKY GM, 1975, FLOW ALGORITHMS
  • [2] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
  • [3] [Anonymous], 1992, COMMENT MATH U CAROL
  • [4] THE CUT CONE, L1 EMBEDDABILITY, COMPLEXITY, AND MULTICOMMODITY FLOWS
    AVIS, D
    DEZA, M
    [J]. NETWORKS, 1991, 21 (06) : 595 - 617
  • [5] ON LIPSCHITZ EMBEDDING OF FINITE METRIC-SPACES IN HILBERT-SPACE
    BOURGAIN, J
    [J]. ISRAEL JOURNAL OF MATHEMATICS, 1985, 52 (1-2) : 46 - 52
  • [6] BRETAGNOLLE J, 1966, ANN I H POINCARE B, V2, P231
  • [7] Dahlhaus E., 1992, Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, P241, DOI 10.1145/129712.129736
  • [8] Deza M., 1992, BSR9221 CWI
  • [9] A NOTE ON THE MAXIMUM FLOW THROUGH A NETWORK
    ELIAS, P
    FEINSTEIN, A
    SHANNON, CE
    [J]. IRE TRANSACTIONS ON INFORMATION THEORY, 1956, 2 (04): : 117 - 119
  • [10] Ford LR, 1956, CAN J MATH, V8, P399, DOI [10.4153/CJM-1956-045-5, DOI 10.4153/CJM-1956-045-5]
1234