We give a bi-criteria approximation algorithm for the Minimum Nonuniform Graph Partitioning problem, recently introduced by Krauthgamer, Naor, Schwartz and Talwar. In this problem, we are given a graph G = (V,E) and k numbers p1, . . . , pk. The goal is to partition V into k disjoint sets (bins) P1, . . . , Pk satisfying |Pi| ≤ pi|V | for all i, so as to minimize the number of edges cut by the partition. Our bi-criteria algorithm gives an O(√log| V | lag k) approximation for the objective function in general graphs and an O(1) approximation in graphs excluding a fixed minor. The approximate solution satisfies the relaxed capacity constraints |Pi| ≤ (5 + ∈) p i|V |. This algorithm is an improvement upon the O(log |V |)-approximation algorithm by Krauthgamer, Naor, Schwartz and Talwar. We extend our results to the case of unrelated weights and to the case of unrelated d-dimensional weights. A preliminary version of this work was presented at the 41st International Colloquium on Automata, Languages and Programming (ICALP 2014).
- approximation algorithm
- approximation for trees
- minimum nonuniform graph partitioning problem
- minimum nonuniform graph partitioning problem with unrelated weights
- semidefinite programming
ASJC Scopus subject areas
- Algebra and Number Theory