The Capacitated Max k-Cut Problem

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.