Non-Uniform Graph Partitioning

Robert Krauthgamer, Joseph Naor, Roy Schwartz, Kunal Talwar

Abstract

We consider the problem of Non-Uniform Graph Partitioning, where the input is an edge-weighted undirected graph G = (V, E) and k capacities n1, …, nk, and the goal is to find a partition {S1, S2, …, Sk} of V satisfying |Sj| ≤ nj for all 1 ≤ j ≤ k, that minimizes the total weight of edges crossing between different parts. This natural graph partitioning problem arises in practical scenarios, and generalizes well-studied balanced partitioning problems such as Minimum Bisection, Minimum Balanced Cut, and Minimum k-Partitioning. Unlike these problems, Non-Uniform Graph Partitioning seems to be resistant to many of the known partitioning techniques, such as spreading metrics, recursive partitioning, and Räcke's tree decomposition, because k can be a function of n and the capacities could be of different magnitudes. We present a bicriteria approximation algorithm for Non-Uniform Graph Partitioning that approximates the objective within O(logn) factor while deviating from the required capacities by at most a constant factor. Our approach is to apply stopping-time based concentration results to a simple randomized rounding of a configuration LP. These concentration bounds are needed as the commonly used techniques of bounded differences and bounded conditioned variances do not suffice.
BibTeX
@inproceedings{krauthgamer2014non,
  author = {Robert Krauthgamer and Joseph Naor and Roy Schwartz and Kunal Talwar},
  title = {{Non-Uniform Graph Partitioning}},
  booktitle = {SODA},
  year = {2014},
  doi = {10.1137/1.9781611973402.91},
}

Loading related content...

Figure