0(\sqrt {\log n)} Approximation to SPARSEST CUT in Õ(n²) Time
Authors:
- 23 December 2004
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 238-247
Abstract
We show how to compute O(/spl radic/log n)-approximations to SPARSEST CUT and BALANCED SEPARATOR problems in O/spl tilde/(n/sup 2/) time, thus improving upon the recent algorithm of Arora, Rao and Vazirani (2004). Their algorithm uses semidefinite programming and required O/spl tilde/(n/sup 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.Keywords
This publication has 17 references indexed in Scilit:
- Expander flows, geometric embeddings and graph partitioning2004
- Approximating Fractional Multicommodity Flow Independent of the Number of CommoditiesSIAM Journal on Discrete Mathematics, 2000
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithmsJournal of the ACM, 1999
- Adaptive Game Playing Using Multiplicative WeightsGames and Economic Behavior, 1999
- Efficient approximation algorithms for semidefinite programs arising from MAX CUT and COLORING1996
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse CutsSIAM Journal on Computing, 1994
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random StartSIAM Journal on Matrix Analysis and Applications, 1992
- A new approach to the maximum-flow problemJournal of the ACM, 1988
- λ1, Isoperimetric inequalities for graphs, and superconcentratorsJournal of Combinatorial Theory, Series B, 1985