## 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