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

Sanjeev Arora; Elad Hazan; Satyen Kale

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

Research output: Contribution to journal › Conference article › peer-review

Abstract

We show how to compute O(√log n)-approximations to SPARSEST CUT and BALANCED SEPARATOR problems in Õ(n ²) 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 language	English (US)
Pages (from-to)	238-247
Number of pages	10
Journal	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
State	Published - 2004
Event	Proceedings - 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004 - Rome, Italy Duration: Oct 17 2004 → Oct 19 2004

All Science Journal Classification (ASJC) codes

General Engineering

Cite this

@article{3086552d91b44dcfa01f3204186ace5c,

title = "O(√log n) approximation to SPARSEST CUT in {\~O}(n 2) time",

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

author = "Sanjeev Arora and Elad Hazan and Satyen Kale",

year = "2004",

language = "English (US)",

pages = "238--247",

journal = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

issn = "0272-5428",

note = "Proceedings - 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004 ; Conference date: 17-10-2004 Through 19-10-2004",

}

TY - JOUR

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

AU - Arora, Sanjeev

AU - Hazan, Elad

AU - Kale, Satyen

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=17744380466&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=17744380466&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:17744380466

SN - 0272-5428

SP - 238

EP - 247

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

T2 - Proceedings - 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004

Y2 - 17 October 2004 through 19 October 2004

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this