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: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: [error in script] 11 (Google Scholar) | [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
Uncontrolled Keywords: heuristics, minimum-cost spanning tree, moat widths
Subjects: UNSPECIFIED
Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 27 Jun 2003 00:00
Last Modified: 19 Jan 2012 10:58
Deposit Information:
ZAIK Number: [error in script]
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