Robust Matchings

Abstract

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\le|M|$ p edges whose total weight is at least ${1\over \sqrt 2}$ of the maximum weight of a p-matching. We use this property to approximate the metric maximum clustering problem with given cluster sizes.