On the existence of weak greedy matching heuristics
We exhibit an exponential number of greedy heuristics for minimum weight perfect matching of complete graphs of n vertices with edge weights satisfying the triangle inequality. The ratio of the weight of an approximate solution obtained by these heuristics to that of an optimal solution is shown to be bounded above by finite and valued functions which depend only on n.
scientific article; zbMATH DE number 3968627