New primal and dual Matching heuristics

Jünger, Michael and Pulleyblank, William R. (1995) New primal and dual Matching heuristics.
Published in: Algorithmica Vol. 13 (4). pp. 357-380.


We describe a new heuristic for constructing a minimum cost perfect matching designed for problems on complete graphs whose cost functions satisfy the triangle inequality (e.g., Euclidean problems). The running time for an n node problem is O(n log n) after a minimum cost spanning tree is constructed. We also describe a procedure which, added to Kruskal's algorithm, produces a lower bound on the size of any perfect matching. This bound is based on a dual problem which has the following geometric interpretation for Euclidean problems: Pack nonoverlapping discs centered at the nodes and moats surrounding odd sets of nodes so as to maximize the sum of the disc radii and moat widths.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Content information:
Deposit Information:
ZAIK Number: zpr91-105
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 27 Jun 2003 00:00
Last Modified: 19 Jan 2012 10:58