期刊
SIAM JOURNAL ON COMPUTING
卷 39, 期 5, 页码 1748-1771出版社
SIAM PUBLICATIONS
DOI: 10.1137/080731049
关键词
graph partitioning; expander flows; multiplicative weights
资金
- David and Lucile Packard Fellowship
- NSF [CCR 0205594, CCR 0098180, MSPA-MCS 0528414]
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].
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据