[ACM Press the sixteenth annual ACM symposium - Barcelona, Spain (2004.06.27-2004.06.30)] Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures - SPAA '04 - Balanced graph partitioning

✍ Scribed by Andreev, Konstantin; Räcke, Harald

• Book ID: 126989406
• Publisher: ACM Press
• Year: 2004
• Tongue: English
• Weight: 127 KB
• Category: Article
• ISBN-13: 9781581138405
• DOI: 10.1145/1007912.1007931

✦ Synopsis

In this paper we consider the problem of (k, ν)-balanced graph partitioning -dividing the vertices of a graph into k almost equal size components (each of size less than ν • n k ) so that the capacity of edges between different components is minimized. This problem is a natural generalization of several other problems such as minimum bisection, which is the (2, 1)-balanced partitioning problem. We present a bicriteria polynomial time approximation algorithm with an O(log 2 n)-approximation for any constant ν > 1. For ν = 1 we show that no polytime approximation algorithm can guarantee a finite approximation ratio unless P = N P . Previous work has only considered the (k, ν)-balanced partitioning problem for ν ≥ 2.