A new class of heuristic algorithms for weighted perfect matching
Michael D. Grigoriadis, Bahman Kalantari · Journal of the ACM · 1988
The minimum-weight perfect matching problem for complete graphs ofnvertices with edge weights satisfying the triangle inequality is considered. For each nonnegative integerk≤ log3n, and for any perfect matching algorithm that runs int(n) time and has an error bound of ƒ(n) times the optimal weight, anO(max{n2,t(3-kn)})-time heuristic algorithm with an error bound of (7/3)k(1 + ƒ(3kn)) - 1 is given. By the selection ofkas appropriate functions ofn, heuristics that have better running times and/or error bounds than existing ones are derived.