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 [J].

AVIS, D ;

DEZA, M .

NETWORKS, 1991, 21 (06) :595-617

[5] ON LIPSCHITZ EMBEDDING OF FINITE METRIC-SPACES IN HILBERT-SPACE [J].

BOURGAIN, 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 [J].

ELIAS, P ;

FEINSTEIN, A ;

SHANNON, CE .

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]

← 1 2 3 4 →