We construct approximation algorithms for graph partitioning problems in which the sizes of the parts are given. These algorithms are based on a theorem stating that in every complete graph with n nodes and nonnegative edge weights there exists a matching such that, for p=1,...,[n/2], the total weight of its heaviest p edges is at least 1/sqrt2 of the weight of a maximum p-matching.

(Joint work with Rubinstein.)