Minimum nonuniform graph partitioning with unrelated weights

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 $\rho_1,\dots, \rho_k$. The goal is to partition $V$ into $k$ disjoint sets (bins) $P_1,\dots, P_k$ satisfying $|P_i|\leq \rho_i |V|$ for all $i$, so as to minimize the number of edges cut by the partition. Our bi-criteria algorithm gives an $O(\sqrt{\log |V| \log 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 $|P_i| \leq (5+ \varepsilon)\rho_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).
Bibliography: 7 titles.