Approximation algorithms for the Weighted t-Uniform Sparsest Cut and some other graph partitioning problems

• An O(log t) bicriteria approximation algorithm for the Weighted t-USC problem.
• The first approximation algorithm with approximation factor independent of n.
• For t=no(1)t=no(1) the algorithm gives the best approximation factor.
• The algorithm is deterministic and requires solving a LP instead of a SDP.
• Approx algorithms for Weighted k-Unbalanced Cut and Min–Max k-Partitioning problems.

We study the Weighted t-Uniform Sparsest Cut (Weighted t-USC) and other related problems. In an instance of the Weighted t-USC problem, a parameter t   and an undirected graph G=(V,E)G=(V,E) with edge-weights w:E→R≥0w:E→R≥0 and vertex-weights η:V→R+η:V→R+ are given. The goal is to find a vertex set S⊆VS⊆V with |S|≤t|S|≤t while minimizing w(S,V\S)/η(S)w(S,V\S)/η(S), where w(S,V\S)w(S,V\S) is the total weight of the edges with exactly one endpoint in S   and η(S)=∑v∈Sη(v)η(S)=∑v∈Sη(v). For this problem, we present a (O(log⁡t),1+ϵ)(O(log⁡t),1+ϵ) factor bicriteria approximation algorithm. Our algorithm outperforms the current best algorithm when t=no(1)t=no(1). We also present better approximation algorithms for Weighted ρ-Unbalanced Cut and Min–Max k-Partitioning problems.