Fast and Simple Algorithms for Weighted Perfect Matching

We present two fast and simple combinatorial approximation algorithms for constructing a minimum-weighted perfect matching on complete graphs whose cost functions satisfy the triangle inequality. The first algorithm runs in O ( n 2 log n ) time and is at most a factor logn worse than an optimal solution. In the second algorithm, the average time until a node is matched is O ( n 2 ) and the approximation ratio is log 2 n .