An approximation algorithm for maxk-uncut with capacity constraints
Salimur Choudhury, Daya Ram Gaur, Ramesh Krishnamurti · Optimization · 2011
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 ≥ 2. We give a 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 .