Approximation Algorithm for Sparsest k-Partitioning

Anand Louis, Konstantin Makarychev

Given a graph $G$, the sparsest-cut problem asks to find the set of vertices $S$ which has the least expansion defined as $$ϕ_G(S) := \frac{w(E(S,\bar{S}))}{\min \set{w(S), w(\bar{…