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.

Abstract

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.


Actions:
Full text not available from this repository.
Export as:
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
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/105