The capacitated max k-cut problem

• 成果类型: Article
• 署名作者: Gaur, Daya Ram; Krishnamurti, Ramesh; Kohli, Rajeev
• 署名单位: Columbia University; Simon Fraser University; University of Lethbridge
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-007-0139-z
• 发表日期: 2008
• 页码: 65-72
• 关键词: improved approximation algorithms; LOCAL SEARCH; bisection

摘要

We consider a capacitated max k-cut problem in which a set of vertices is partitioned into k subsets. Each edge has a non-negative weight, and each subset has a possibly different capacity that imposes an upper bound on its size. The objective is to find a partition that maximizes the sum of edge weights across all pairs of vertices that lie in different subsets. We describe a local-search algorithm that obtains a solution with value no smaller than 1 - 1/k of the optimal solution value. This improves a previous bound of 1/2 for the max k-cut problem with fixed, though possibly different, sizes of subsets.