45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04) 0(\sqrt {\log n)} Approximation to SPARSEST CUT in ?(n²) Time Rome, Italy October 17-October 19 ISBN: 0-7695-2228-9
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 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb