Fast algorithm finds near-best pairings of points in the plane
A new O(n log n) approach for the Euclidean maximum weight matching problem
Computational Geometry
Summary
Matching points in a plane to maximize distances between pairs is a tricky problem that usually takes a long time to solve exactly. The authors have designed an algorithm that finds very good or optimal pairings much faster, running in time proportional to the number of points times the logarithm of that number. Their tests show that this method produces solutions very close to the best possible, making it useful when exact methods are too slow for large sets of points. This approach balances speed and accuracy well for practical use.
maximum weight matchingEuclidean distancepairing problemgraph theoryalgorithm complexityapproximation algorithmsubquadratic timecombinatorial optimization
Authors
Rostislav Staněk, Robert Arustamyan
Abstract
In a weighted graph $G = (V, E)$, the maximum weight matching problem (MWM) asks for a matching (i.e. pairing) of its vertices, such that each vertex is paired with at most one other vertex and the total sum of weights of all edges connecting paired vertices is maximised. If the vertices of the graph correspond to points in the Euclidean plane and the weights to their pairwise Euclidean distances, we get the Euclidean maximum weight matching problem (Euclidean MWM). The best optimum-solution algorithm for this problem runs in $O(n^{2.5})$. Furthermore, there exists an FPTAS guaranteeing a $(1 - ε)$-approximation ratio, which runs in $O(m ε^{-1} \log ε^{-1})$ time. Heuristics with a subquadratic running time (with respect to the number of vertices $|V|$) are known, but often yield solutions of a modest quality. In this paper, we present a novel algorithm for solving the Euclidean MWM running in $O(n \log n)$ time and providing excellent solution quality, especially for larger instances. In particular, in our computational tests, the algorithm yielded optimum or near-optimum solutions for all test instances; the worst observed optimality gap was less than $1.38\%$. This makes the algorithm highly attractive for practical applications, especially when exact methods become computationally prohibitive due to the size of the instance.