O(√log n) APPROXIMATION TO SPARSEST CUT IN (O)over-bar(n2) TIME

被引：29

作者：

Arora, Sanjeev ^{[1
]}

Hazan, Elad ^{[2
]}

Kale, Satyen ^{[3
]}

机构：

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

[2] IBM Almaden, San Jose, CA 95120 USA

[3] Yahoo Res, Santa Clara, CA 95054 USA

来源：

SIAM JOURNAL ON COMPUTING | 2010年 / 39卷 / 05期

关键词：

graph partitioning; expander flows; multiplicative weights; CONCURRENT FLOW PROBLEM; ALGORITHMS; GRAPHS;

D O I：

10.1137/080731049

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper shows how to compute O(root log n)-approximations to the SPARSEST CUT and BALANCED SEPARATOR problems in (O) over tilde (n(2)) time, thus improving upon the recent algorithm of Arora, Rao, and Vazirani [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222-231]. Their algorithm uses semidefinite programming and requires (O) over tilde (n(9.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 [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222-231].

引用

页码：1748 / 1771

页数：24

共 31 条

[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], 1970, Problems in Analysis

[5]

[Anonymous], 1997, AM MATH SOC

[6]

ARORA S, THEORY COMPUT UNPUB

[7]

Arora S., 2004, P 36 ANN S THEORY CO, P222

[8] A Combinatorial, Primal-Dual Approach to Semidefinite Programs [J].

Arora, Sanjeev ;

Kale, Satyen .

STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, 2007, :227-236

[9] 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

[10]

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

← 1 2 3 4 →