Matthias Kaiserswerth
IEEE/ACM Transactions on Networking
This paper shows how to compute O(√log n)-approximations to the sparsest Cut and Balanced Separator problems in Õ(n2) time, thus improving upon the recent algorithm of Arora, Rao, and Vazirani [Proceedings of the 336th Annual ACM Symposium on Theory of Computing, 2004, pp. 222-231]. Their algorithm uses semidefinite programming and requires Õ(n9.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]. © 2010 Society for Industrial and Applied Mathematics.
Matthias Kaiserswerth
IEEE/ACM Transactions on Networking
Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
Minkyong Kim, Zhen Liu, et al.
INFOCOM 2008
Kaoutar El Maghraoui, Gokul Kandiraju, et al.
WOSP/SIPEW 2010