Abstract
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
.