Partitioning graphs into balanced components

We consider the k-balanced partitioning problem, where the goal is to partition the vertices of an input graph G into k equally sized components, while minimizing the total weight of the edges connecting different components. We allow k to be part of the input and denote the cardinality of the vertex set by n. This problem is a natural and important generalization of well-known graph partitioning problems, including minimum bisection and minimum balanced cut. We present a (bi-criteria) approximation algorithm achieving an approximation of, which matches or improves over previous algorithms for all relevant values of k. Our algorithm uses a semidefinite relaxation which combines metrics with spreading metrics. Surprisingly, we show that the integrality gap of the semidefinite relaxation is Ω(log k ) even for large values of k (e. g. , k = n Ω(1) ), implying that the dependence on k of the approximation factor is necessary. This is in contrast to previous approximation algorithms for k -balanced partitioning, which are based on linear programming relaxations and their approximation factor is independent of k.

Authors

• Robert Krauthgamer
• Joseph Naor
• Roy Schwartz 0002

Keywords

No keywords are indexed for this paper.