Non-Uniform Graph Partitioning

Robert Krauthgamer, Joseph Naor, Roy Schwartz, Kunal Talwar

TL;DR

This paper introduces a novel bicriteria approximation algorithm for the Non-Uniform Graph Partitioning problem, which aims to divide a graph into parts with varying capacity constraints while minimizing edge cuts. The algorithm achieves an O(log n) approximation for the cut cost while ensuring part sizes deviate from their capacities by at most a constant factor, a significant improvement over existing methods that struggle with non-uniform capacities.

What Problem Does This Paper Address?

Graph partitioning is a fundamental problem with applications in parallel computing, data mining, and VLSI design. Traditional graph partitioning problems, like Minimum Bisection or Minimum k-Partitioning, assume uniform capacity constraints for all resulting parts. However, many real-world scenarios require partitioning into parts with different capacity limits. This "Non-Uniform Graph Partitioning" problem is significantly harder because standard techniques like spreading metrics, recursive partitioning, and tree decompositions fail when capacities vary widely or when the number of parts is large. The paper tackles the challenge of finding a provably good solution for this more general and practical problem.

Methods

The authors propose a bicriteria approximation algorithm that combines several key techniques:

  • Instance Simplification: The algorithm first simplifies the capacity constraints by rounding them to powers of two and then "clumping" them into "mega-buckets." This step is crucial for bounding the capacity violation later.
  • Configuration LP: A fractional relaxation of the problem is formulated as a Linear Program (LP). The authors develop an algorithm to approximately solve this LP, achieving a solution that is close to optimal in cost and only slightly violates the capacity constraints.
  • Randomized Rounding with Stopping Times: A novel randomized rounding technique is employed. Instead of standard concentration bounds, the algorithm uses stopping-time based concentration results. This allows for a more precise analysis of the capacity violation, leading to a constant factor bound. The core idea is to analyze the behavior of a martingale process and bound its variance using conditioned variances, which is more robust than traditional methods.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The Challenge of Non-Uniformity: The paper highlights why standard graph partitioning techniques break down when capacities are non-uniform. The "spreading" nature of many algorithms leads to solutions that are too uniform, failing to respect vastly different capacity requirements.
  • The Power of Instance Simplification: By transforming the capacity constraints into a more structured form (powers of two, mega-buckets), the problem becomes more amenable to analysis, particularly for bounding capacity violations.
  • Martingale Concentration for Bounded Violation: The use of stopping-time based martingale concentration is a key innovation. It allows for a tighter bound on the capacity violation than traditional methods, which often lead to multiplicative violations dependent on the number of parts or capacities.
  • Bicriteria Approach is Necessary: The problem inherently requires a bicriteria approximation (balancing cut cost and capacity violation), and the authors demonstrate how to achieve good bounds for both simultaneously.

Key Results

The paper presents a polynomial-time algorithm that achieves:

  • An approximation factor of O(log n) for the total weight of edges crossing between different parts.
  • A capacity violation of at most a constant factor for each part.

This is a significant theoretical result, as it provides the first provable guarantee for the Non-Uniform Graph Partitioning problem with a constant capacity violation.

Limitations and Future Work

  • Constant Factor for Capacity Violation: While the paper achieves a constant factor for capacity violation, the specific constant is not optimized and could potentially be improved. The authors mention deferring the analysis for optimizing this constant to a full version of the paper.
  • Practical Performance: The paper focuses on theoretical guarantees. The practical performance of the proposed algorithm and its comparison to existing heuristics on real-world instances are not discussed.
  • Further Exploration of Techniques: The authors suggest that the techniques developed, particularly the martingale concentration via stopping times, could be applicable to other related problems.

Summary updated

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},
}
Figure