A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut

Vladimir Kolmogorov

Currently, the best known tradeoff between approximation ratio and complexity for the Sparsest Cut problem is achieved by the algorithm in [Sherman, FOCS 2009]: it computes $O(\sqr…