A fast algorithm for Euclidean maximum weight non-bipartite matching

The maximum weight matching (MWM) on general, non-bipartite, graphs is solvable in polynomial time. Yet none of the exact optimization algorithms for the problem scales well enough for dealing with large data sets. We present here a heuristic algorithm for solving MWM on graphs where the nodes are vectors in a d-dimensional space and the edge weights are Euclidean distances or distances induced by any other metric norm. The algorithm is based on a recent anticlustering method called Assignment-Based Anticlustering (ABA) that for anticlusters of size 2 generates a maximum weight matching of high quality, often within less than 1% of the optimum, at a speed that is several orders of magnitude faster than exact optimization algorithms, and other heuristic algorithms. This significant performance advantage makes the ABA algorithm a powerful tool for large-scale geometric applications.