[en] 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 ${\mathrm{\rho <!--\; ??\; -->}}_1,\dots <!--\; ???\; -->,{\mathrm{\rho <!--\; ??\; -->}}_k$. The goal is to partition $V$ into $k$ disjoint sets (bins) $P_1,\dots <!--\; ???\; -->,P_k$ satisfying $|P_i|\le <!--\; ???\; -->{\mathrm{\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|\le <!--\; ???\; -->(5+\mathrm{\epsilon <!--\; ??\; -->}){\mathrm{\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. (paper)