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).


  • thumnail for 1997_Imielinska_Algorithmica_Kalantari.pdf 1997_Imielinska_Algorithmica_Kalantari.pdf application/pdf 296 KB Download File

Also Published In


More About This Work

Academic Units
Biomedical Informatics
Published Here
September 29, 2014