A new class of heuristic algorithms for weighted perfect matching

The minimum-weight perfect matching problem for complete graphs of n vertices with edge weights satisfying the triangle inequality is considered. For each nonnegative integer k•log3n, and for any perfect matching algorithm that runs in t(n) time and has an error bound of f(n) times the optimal weight, an O(max{n²,t(3’-’kn)})-time heuristic algorithm with an error bound of (7/3)^k(1+f(3’-^kn))-1 is given. By the selection of k as appropriate functions of n, heuristics that have better running times and/or error bounds than existing ones are derived.