Approximation Algorithm for Sparsest k-Partitioning

2013/06/18 by Louis, Anand, Makarychev, Konstantin
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1306.4384

Abstract

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) := \fracw(E(S,S))min \setw(S), w(S), 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 \setP₁, …, P_k of the vertex set so as to minimize ϕ_k(\setP₁, …, P_k) := max_i ϕ_G(P_i). Our main result is a polynomial time bi-criteria approximation algorithm which outputs a (1 - \e)k-partition of the vertex set such that each piece has expansion at most O_ε(√(log n log k)) times OPT. We also study balanced versions of this problem.

Related

• Approximating Small Sparse Cuts
• Fixed Parameter Approximation Scheme for Min-max k-cut
• Min-Max Graph Partitioning and Small Set Expansion
• Approximation and parameterized algorithms to find balanced connected partitions of graphs
• Planted Models for k-way Edge and Vertex Expansion