$O(\sqrt{\logn})$ Approximation to SPARSEST CUT in $\tilde{O}(n^2)$ Time
Sanjeev Arora, Elad Hazan, Satyen Kale · SIAM Journal on Computing · 2010
This paper shows how to compute $O(\sqrt{\log n})$-approximations to the Sparsest Cut and Balanced Separator problems in $\tilde{O}(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 $\tilde{O}(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].