Approximation algorithms for minimum K-cut

Let G = (V, E) be a complete undirected graph, with node set V = {v(1),..., v(n)} and edge set E. The. edges (vi, vi) E E have nonnegative weights that satisfy the triangle inequality. Given a set of integers K = {k(i)}(i=1)(p ) (Sigma(i=1)(p) k(i) less than or equal to \V\), the minimum K-cut problem is to compute disjoint subsets with sizes {k(i)}(i=1)(p), minimizing the t otal weight of edges whose two ends are in different subsets. We demonstrat e that for any fixed p it is possible to obtain in polynomial time an appro ximation of at most three times the optimal value. We also prove bounds on the ratio between the weights of maximum and minimum cuts.