1997 Articles

A General Class of Heuristics for Minimum Weight Perfect Matching and Fast Special Cases with Doubly and Triply Logarithmic Errors

Imielinska, Celina Z.; Kalantari, B.

We give a class of heuristic algorithms for minimum weight perfect matching on a complete edgeweighted graph K(V) satisfying the triangle inequality, where V is a set of an even number, n, of vertices.This class is a generalization of the Onethird heuristics, the hypergreedy heuristic, and it possibly employs any given exact or approximate perfect matching algorithm as an auxiliary heuristic to an appropriate subgraph of K(V).