Approximation algorithms for the Weighted t-Uniform Sparsest Cut and some other graph 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 ) with edge-weights w : E → R ≥ 0 and vertex-weights η : V → R + are given. The goal is to find a vertex set S ⊆ V with | S | ≤ t while minimizing w ( S , V \ S ) / η ( S ) , where w ( S , V \ S ) is the total weight of the edges with exactly one endpoint in S and η ( S ) = ∑ v ∈ S η ( v ) . For this problem, we present a ( O ( log ⁡ t ) , 1 + ϵ ) factor bicriteria approximation algorithm. Our algorithm outperforms the current best algorithm when t = n o ( 1 ) . We also present better approximation algorithms for Weighted ρ -Unbalanced Cut and Min–Max k -Partitioning problems. [ABSTRACT FROM AUTHOR]