Min-Max Graph Partitioning
May 9, 2012
ABSTRACT:
Motivated by applications in cloud computing, we study the following min-max graph partitioning problem. Given an n-vertex undirected graph G and a value k, find a partition of the vertices into k equal-sized parts that minimizes the maximum number of edges leaving any single part. We provide an O(sqrt{log n log k})-approximation algorithm for this problem, that violates the size constraints by at most a constant factor. On graphs that exclude some fixed minor, we provide an improved constant factor approximation.
Motivated by applications in cloud computing, we study the following min-max graph partitioning problem. Given an n-vertex undirected graph G and a value k, find a partition of the vertices into k equal-sized parts that minimizes the maximum number of edges leaving any single part. We provide an O(sqrt{log n log k})-approximation algorithm for this problem, that violates the size constraints by at most a constant factor. On graphs that exclude some fixed minor, we provide an improved constant factor approximation.