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 &le 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{n2,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.