We introduce a capacitated max k-cut problem in which a set of vertices is partitioned into k subsets, each with a possibly different capacity. The objective is to maximize the weighted number of edges across subsets when a weight is associated with each edge of the graph. We describe a switching algorithm that obtains a solution which is at least 1?(1/k) of the optimal solution.
Mathematical Programming (A)vol.
115, (September 01, 2008):