Minimum nonuniform graph partitioning with unrelated weights

K. S. Makarychev, Yu S. Makarychev

Research output: Contribution to journalArticlepeer-review

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 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).

Original languageEnglish (US)
Pages (from-to)1835-1853
Number of pages19
JournalSbornik Mathematics
Volume208
Issue number12
DOIs
StatePublished - 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

  • Algebra and Number Theory

Fingerprint Dive into the research topics of 'Minimum nonuniform graph partitioning with unrelated weights'. Together they form a unique fingerprint.

Cite this