O(√log n) approximation to SPARSEST CUT in Õ(n 2) time

Research output: Contribution to journalConference article

29 Scopus citations

Abstract

We show how to compute O(√log n)-approximations to SPARSEST CUT and BALANCED SEPARATOR problems in Õ(n 2) time, thus improving upon the recent algorithm of Arora, Rao and Vazirani (2004). Their algorithm uses semidefinite programming and required Õ(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.

Original languageEnglish (US)
Pages (from-to)238-247
Number of pages10
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
StatePublished - Dec 1 2004
EventProceedings - 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004 - Rome, Italy
Duration: Oct 17 2004Oct 19 2004

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Cite this