O(√log n) approximation to sparsest cut in õ(n2) time

Research output: Contribution to journalArticlepeer-review

35 Scopus citations

Abstract

This paper shows how to compute O(√log n)-approximations to the sparsest Cut and Balanced Separator problems in Õ(n2) time, thus improving upon the recent algorithm of Arora, Rao, and Vazirani [Proceedings of the 336th Annual ACM Symposium on Theory of Computing, 2004, pp. 222-231]. Their algorithm uses semidefinite programming and requires Õ(n9.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].

Original languageEnglish (US)
Pages (from-to)1748-1771
Number of pages24
JournalSIAM Journal on Computing
Volume39
Issue number5
DOIs
StatePublished - 2010

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics

Keywords

  • Expander flows
  • Graph partitioning
  • Multiplicative weights

Fingerprint

Dive into the research topics of 'O(√log n) approximation to sparsest cut in õ(n2) time'. Together they form a unique fingerprint.

Cite this