Approximation Algorithm for Sparsest k -Partitioning

Given a graph G, the sparsest-cut problem asks to find the set of vertices S which has the least expansion defined as where w is the total edge weight of a subset. Here we study the natural generalization of this problem: given an integer k, compute a k -partition { P 1, …, P k } of the vertex set so as to minimize Our main result is a polynomial time bi-criteria approximation algorithm which outputs a (1 – ∊ ) k -partition of the vertex set such that each piece has expansion at most times OPT. We also study balanced versions of this problem.

Authors

• Anand Louis
• Konstantin Makarychev

Keywords

No keywords are indexed for this paper.