Breaking the Multicommodity Flow Barrier for sqrt(log(n))-Approximations to Sparsest Cut

Jonah Sherman

This paper ties the line of work on algorithms that find an O(sqrt(log(n)))-approximation to the sparsest cut together with the line of work on algorithms that run in sub-quadratic…