An approximation algorithm for max k-uncut with capacity constraints

作者：Choudhury Salimur^*; Gaur Daya R; Krishnamurti Ramesh

来源：Optimization, 2012, 61(2): 143-150.

DOI：10.1080/02331934.2011.592527

• max k-uncut
• capacity constraints
• local search
• unbalanced partition

Given an edge-weighted graph the problem is to partition the vertices of the graph into k partitions of prescribed sizes such that the total weight of the edges within partitions are maximized. This problem is NP-complete for all k %26gt;= 2. We give a 1/d (k - 1) + 1 factor approximation where d is the ratio of the largest size and the smallest size in the partition. When the number of partitions k is 2, we give an approximation algorithm with performance ratio 1/3.

• 出版日期2012