Academic Commons

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

Files

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

Also Published In

Title
Algorithmica

More About This Work

Academic Units
Biomedical Informatics
Publisher
Springer-Verlag
Published Here
September 29, 2014
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.