O(√log n) approximation to SPARSEST CUT in (O)over-tilde(n2) time

被引：25

作者：

Arora, S ^{[1
]}

Hazan, E ^{[1
]}

Kale, S ^{[1
]}

机构：

[1] Princeton Univ, Dept Comp Sci, Princeton, NJ 08544 USA

来源：

45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 2004年

关键词：

D O I：

10.1109/FOCS.2004.1

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show how to compute O(rootlog n)-approximations to SPARSEST CUT and BALANCED SEPARATOR problems in O(n(2)) time, thus improving upon the recent algorithm of Arora, Rao and Vazirani (2004). Their,algorithm uses semidefinite programming and required O(n(4.5)) time. Our algorithm relies on efficiently finding expander flows in the graph and does not solve semidefinite programs. The existence of expander flows was also established by Arora, Rao, and Vazirani.

引用

页码：238 / 247

页数：10

共 25 条

[1] INTERIOR-POINT METHODS IN SEMIDEFINITE PROGRAMMING WITH APPLICATIONS TO COMBINATORIAL OPTIMIZATION [J].

ALIZADEH, F .

SIAM JOURNAL ON OPTIMIZATION, 1995, 5 (01) :13-51

[2] LAMBDA-1, ISOPERIMETRIC-INEQUALITIES FOR GRAPHS, AND SUPERCONCENTRATORS [J].

ALON, N ;

MILMAN, VD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 38 (01) :73-88

[3] EIGENVALUES AND EXPANDERS [J].

ALON, N .

COMBINATORICA, 1986, 6 (02) :83-96

[4]

[Anonymous], 1997, CBMS REG C SER MATH

[5]

Arora S., 2004, P 36 ANN ACM S THEOR, P222, DOI [DOI 10.1145/1007352.1007355, 10.1145/1007352.1007355]

[6] An O(log k) approximate min-cut max-flow theorem and approximation algorithm [J].

Aumann, Y ;

Rabani, Y .

SIAM JOURNAL ON COMPUTING, 1998, 27 (01) :291-301

[7]

Benczur A. A., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, P47, DOI 10.1145/237814.237827

[8] THE COMPLEXITY OF TESTING WHETHER A GRAPH IS A SUPERCONCENTRATOR [J].

BLUM, M ;

KARP, RM ;

VORNBERGER, O ;

PAPADIMITRIOU, CH ;

YANNAKAKIS, M .

INFORMATION PROCESSING LETTERS, 1981, 13 (4-5) :164-167

[9]

CHAWLA S, 2004, UNPUB EMBEDDINGS NEG

[10]

Cheeger J., 1969, Problems in Analysis, P195

← 1 2 3 →