Fast and Simple Algorithms for Weighted Perfect Matching
Mirjam Wattenhofer, Roger P. Wattenhofer · 2004
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 rst algorithm runs in O(n2 log n) time and is at most a factor log n worse than an optimal solution. In the second algorithm, the average time until a node is matched is O(n2) and the approximation ratio is log2 n.