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 t(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.