The Capacitated Max k-Cut Problem
Coauthor(s): Daya Gaur, Ramesh Krishnamurti.
Adobe Acrobat PDF
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.
Source: Mathematical Programming (A)
Gaur, Daya, Ramesh Krishnamurti, and Rajeev Kohli. "The Capacitated Max k-Cut Problem." Mathematical Programming (A) 115, no. 1 (September 2008): 65-72.