Nonuniform graph partitioning with unrelated weights

Konstantin Makarychev, Yury Makarychev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


We give a bi-criteria approximation algorithm for the Minimum Nonuniform Partitioning problem, recently introduced by Krauthgamer, Naor, Schwartz and Talwar (2014). In this problem, we are given a graph G = (V,E) on n vertices and k numbers ρ1,..., ρk. The goal is to partition the graph into k disjoint sets P1,..., Pk satisfying |Pi| ≤ ρin so as to minimize the number of edges cut by the partition. Our algorithm has an approximation ratio of O(√log n log k)for general graphs, and an O(1) approximation for graphs with excluded minors. This is an improvement upon the O(logn) algorithm of Krauthgamer, Naor, Schwartz and Talwar (2014). Our approximation ratio matches the best known ratio for the Minimum (Uniform) k-Partitioning problem. We extend our results to the case of "unrelated weights" and to the case of "unrelated d-dimensional weights". In the former case, different vertices may have different weights and the weight of a vertex may depend on the set Pi the vertex is assigned to. In the latter case, each vertex u has a d-dimensional weight r(u,i) = (r1(u,i),..., rd (u,i)) if u is assigned to Pi. Each set Pi has a d-dimensional capacity c(i) = (c1(i),..., cd (i)). The goal is to find a partition such that ∑u∈Pi r(u, i) ≤ c(i) coordinate-wise.

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings
PublisherSpringer Verlag
Number of pages11
EditionPART 1
ISBN (Print)9783662439470
StatePublished - 2014
Event41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 - Copenhagen, Denmark
Duration: Jul 8 2014Jul 11 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume8572 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other41st International Colloquium on Automata, Languages, and Programming, ICALP 2014

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


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

Cite this