Rajeev Kohli

The Capacitated Max k-Cut Problem

Coauthor(s): Daya Gaur, Ramesh Krishnamurti.

Download:

Adobe Acrobat PDF

Abstract:
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)
Exact Citation:
Gaur, Daya, Ramesh Krishnamurti, and Rajeev Kohli. "The Capacitated Max k-Cut Problem." Mathematical Programming (A) 115, no. 1 (September 2008): 65-72.
Volume: 115
Number: 1
Pages: 65-72
Date: 9 2008

Close Window