We consider the problem of partitioning a graph into k components of roughly equal size while minimizing the capacity of the edges between different components of the cut. In particular we require that for a parameter \nu \ge 1, no component contains more than \nu\cdot\frac{n}{k} of the graph vertices.
For k=2 and \nu=1 this problem is equivalent to the well known Minimum Bisection Problem for which an approximation algorithm with a polylogarithmic approximation guarantee has been presented in [FK02]. For arbitrary k and \nu\ge 2 a bicriteria approximation ratio of O(\log n) was obtained by [ENRS99] using the spreading metrics technique.
We present a bicriteria approximation algorithm that for any constant \nu > 1 runs in polynomial time and guarantees an approximation ratio of O(\log^{1.5}n) (for a precise statement of the main result see \lref{Theorem}{Thm:main}). For \nu =1 and k \geq 3 we show that no polynomial time approximation algorithm can guarantee a finite approximation ratio unless P=NP.