Paper Info
Title
Heuristics for weighted perfect matching
Abstract
The problem of finding near optimal perfect matchings of an even number n of vertices is considered. When the distances between the vertices satisfy the triangle inequality it is possible to get within a constant multiplicative factor of the optimal matching in time O(n2 log K) where K is the ratio of the longest to the shortest distance between vertices. Other heuristics are analyzed as well, including one that gets within a logarithmic factor of the optimal matching in time O(n2 log n). Finding an optimal weighted matching requires &thgr;(n3) time by the fastest known algorithm, so these heuristics are quite useful. When the n vertices lie in the unit (Euclidean) square, no heuristic can be guaranteed to produce a matching of cost less than [equation] in the worst case. We analyze various heuristics for this case, including one that always produces a matching costing at most [equation]. In addition, this heuristic also finds a traveling salesman tour of the n vertices costing at most [equation]. A different one of the heuristics analyzed produces asymptotically optimal results. It is also shown that asymptotically optimal traveling salesman tours can be found in O(n log n) time in the unit square.
Year
DOI
Venue
1980
10.1145/800141.804689
STOC
Keywords
Field
DocType
n vertex,optimal perfect matchings,salesman tour,optimal matching,asymptotically optimal,time o,n log n,number n,weighted perfect matching,n2 log n,asymptotically optimal result,traveling salesman,boolean expression,triangle inequality,satisfiability,space complexity
Discrete mathematics,Combinatorics,Vertex (geometry),Optimal matching,Matching (graph theory),Heuristics,Travelling salesman problem,Triangle inequality,Unit square,Asymptotically optimal algorithm,Mathematics
Conference
ISBN
Citations 
PageRank 
0-89791-017-6
17
10.18
References 
Authors
4
3
Name
Order
Citations
PageRank
Kenneth J. Supowit1698145.71
David A. Plaisted21680255.36
Edward M. Reingold32214563.65