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.
No takes yet. Share an insight, caveat, or question.
Krauthgamer et al. (2009) studied this question.