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 is conteined in V with ∣S∣ ≤ t while minimizing w(S, VS)/η(S), where w(S, VS) 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 p-Unbalanced Cut and Min-Max k-Partitioning problems.