Arnold.L. Rosenberg
Journal of the ACM
We show that the sparsest cut in graphs with n vertices and m edges can be approximated within O(log 2 n) factor in (m + n 3/2) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows that take time (m + n 2). Our algorithm iteratively employs max-flow computations to embed an expander flow, thus providing a certificate of expansion. Our technique can also be extended to yield an O(log 2 n)-(pseudo-) approximation algorithm for the edge-separator problem with a similar running time. © 2009 ACM.
Arnold.L. Rosenberg
Journal of the ACM
Freddy Lécué, Jeff Z. Pan
IJCAI 2013
Jihun Yun, Peng Zheng, et al.
ICML 2019
Albert Atserias, Anuj Dawar, et al.
Journal of the ACM