0(\sqrt {\log n)} Approximation to SPARSEST CUT in ?(n²) Time

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Sanjeev Arora Articles by Elad Hazan Articles by Satyen Kale

45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04)

Rome, Italy

October 17-October 19

ISBN: 0-7695-2228-9

	ASCII Text	x
	Sanjeev Arora, Elad Hazan, Satyen Kale, "0(\sqrt {\log n)} Approximation to SPARSEST CUT in ?(n²) Time," Foundations of Computer Science, Annual IEEE Symposium on, pp. 238-247, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004.

	BibTex	x
	@article{ 10.1109/FOCS.2004.1, author = {Sanjeev Arora and Elad Hazan and Satyen Kale}, title = {0(\sqrt {\log n)} Approximation to SPARSEST CUT in ?(n²) Time}, journal ={Foundations of Computer Science, Annual IEEE Symposium on}, volume = {0}, year = {2004}, issn = {0272-5428}, pages = {238-247}, doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.1}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Foundations of Computer Science, Annual IEEE Symposium on TI - 0(\sqrt {\log n)} Approximation to SPARSEST CUT in ?(n²) Time SN - 0272-5428 SP238 EP247 A1 - Sanjeev Arora, A1 - Elad Hazan, A1 - Satyen Kale, PY - 2004 KW - null VL - 0 JA - Foundations of Computer Science, Annual IEEE Symposium on ER -

Sanjeev Arora, Princeton University

Elad Hazan, Princeton University

Satyen Kale, Princeton University

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.1

We show how to compute 0(\sqrt {\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.

Citation:

Sanjeev Arora, Elad Hazan, Satyen Kale, "0(\sqrt {\log n)} Approximation to SPARSEST CUT in ?(n²) Time," focs, pp.238-247, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.