Journal
SIAM JOURNAL ON COMPUTING
Volume 39, Issue 5, Pages 1748-1771Publisher
SIAM PUBLICATIONS
DOI: 10.1137/080731049
Keywords
graph partitioning; expander flows; multiplicative weights
Funding
- David and Lucile Packard Fellowship
- NSF [CCR 0205594, CCR 0098180, MSPA-MCS 0528414]
Ask authors/readers for more resources
This paper shows how to compute O(root log n)-approximations to the SPARSEST CUT and BALANCED SEPARATOR problems in (O) over tilde (n(2)) time, thus improving upon the recent algorithm of Arora, Rao, and Vazirani [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222-231]. Their algorithm uses semidefinite programming and requires (O) over tilde (n(9.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].
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available