## Abstract

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 p_{1}, . . . , p_{k}. The goal is to partition V into k disjoint sets (bins) P_{1}, . . . , P_{k} satisfying |P_{i}| ≤ p_{i}|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 |P_{i}| ≤ (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).

Original language | English (US) |
---|---|

Pages (from-to) | 1835-1853 |

Number of pages | 19 |

Journal | Sbornik Mathematics |

Volume | 208 |

Issue number | 12 |

DOIs | |

State | Published - 2017 |

## Keywords

- approximation algorithm
- approximation for trees
- minimum nonuniform graph partitioning problem
- minimum nonuniform graph partitioning problem with unrelated weights
- semidefinite programming

## ASJC Scopus subject areas

- Mathematics (miscellaneous)