Robust Matchings, Maximum Clustering, and Maximum Capacitated Medians

We consider complete graphs with nonnegative edge weights. A p-matching is a set of p disjoint edges. We prove the existence of a maximal (with respect to inclusion) matching M that contains for any p jM j p edges whose total weight is at least 1 p 2 of the maximum weight of a p-matching. We use this property to approximate two graph partitioning problems in which the sizes of the parts of the partitioning are given. In one the goal is to maximize the total edge weight within the same cluster. The other one also requires to locate a center within each cluster and the goal is to maximize the total distance from each vertex to its center. AMS subject classification: 05C70 Factorization, matching, covering and packing; 05C85 Graph algorithms. 1 Introduction Let G = (V; E) be a complete graph with vertex set V such that jV j = n, edge set E, and edge weights w(u; v) 0; (u; v) 2 E. A p-matching is a set of p disjoint edges in a graph. A p-matching with p = b n 2 c is called perf..