Approximation algorithms for the metric maximum clustering problem with given cluster sizes

The input to the metric maximum clustering problem with given cluster sizes consists of a complete graph G = (V, E) with edge weights satisfying the triangle inequality, and integers c1, ... , cp that sum to |V|. The goal is to find a partition of V into disjoint clusters of sizes c1, ... , cp, that maximizes the sum of weights of edges whose two ends belong to the same cluster. We describe approximation algorithms for this problem.