On a Greedy Heuristic for Complete Matching

Finding a minimum weighted complete matching on a set of vertices in which the distances satisfy the triangle inequality is of general interest and of particular importance when drawing graphs on a mechanical plotter. The “greedy” heuristic of repeatedly matching the two closest unmatched points can be implemented in worst-case time O(n² log n), a reasonable savings compared to the general minimum weighted matching algorithm which requires time proportional to n³ to find the minimum cost matching in a weighted graph. We show that, for an even number n of vertices whose distances satisfy the triangle inequality, the ratio of the cost of the matching produced by this greedy heuristic to the cost of the minimal matching is at most ₃⁴ n₂³ - 1, ₂³ ≈ 0.58496, and there are examples that achieve this bound. We conclude that this greedy heuristic, although desirable because of its simplicity, would be a poor choice for this problem.