Source-linked AI summary
A new O(n log n) approach for the Euclidean maximum weight matching problem
Rostislav Staněk, Robert Arustamyan
TL;DR
The Euclidean maximum weight matching problem asks for pairings of planar points that maximize total distance, but no faster worst-case optimum or approximation algorithm was known. This paper presents a 2-dimensional O(n log n) algorithm; tests report near-optimal or optimal solutions whose quality improves with instance size, alongside substantially faster running time than known optimum-solution algorithms.
Problem
No optimum or approximation algorithm with a better worst-case running time was known for Euclidean MWM, while existing heuristics often yield solutions much worse than optimum.
Source: §1 · p. 2Method
The paper presents a novel algorithm for the 2-dimensional Euclidean MWM with a guaranteed O(n log n) worst-case running time.
Source: §1 · p. 2Results
The algorithm produces near-optimal or optimal solutions whose quality improves with instance size across the tested instance types, while running substantially faster than known optimal-solution algorithms.
Source: §4 · p. 10Takeaways & Limitations
Its near-optimal performance and O(n log n) running time make it attractive for large and very large instances where exact methods quickly become computationally prohibitive.
Source: §4 · p. 11Asymptotic optimality remains a conjecture; a complete proof for uniformly distributed points in a circle and for the general case is under investigation.
Source: §4 · p. 11
Abstract
from arXiv · showhide
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 - \epsilon)$-approximation ratio, which runs in $O(m \epsilon^{-1} \log \epsilon^{-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.
1 Introduction
The Euclidean maximum weight matching problem seeks pairings of planar points that maximize total Euclidean distance. Although general matching algorithms and faster heuristics exist, no optimum or approximation algorithm with a better worst-case running time was known for this problem; the paper introduces a practical O(n log n) algorithm with excellent solution quality.
- The MWM has practical applications in social sciences, semiconductor manufacturing, and preprocessing for large sparse linear-system solvers.The paper also notes applications related to maximum cardinality minimum weight matching.Source: §1 · pp. 1–2
- The Euclidean MWM has no known optimum or approximation algorithm with a better worst-case running time, while existing heuristics often yield solutions much worse than optimum.The general MWM optimum algorithm runs in O(n^2.5), and an FPTAS runs in O(m ε^-1 log ε^-1).Source: §1 · p. 2
- For planar points, the Euclidean MWM seeks a matching that maximizes the sum of paired-point Euclidean distances.An optimum is perfect when the number of points is even and near-perfect when it is odd.Source: §1 · p. 2
- The paper presents a practical algorithm for the 2-dimensional Euclidean MWM with a worst-case running time of O(n log n) and excellent solution quality.The authors conjecture that its solutions approach the optimum as n tends to infinity.Source: §1 · p. 2
2 Our algorithm
The algorithm reduces Euclidean matching to an optimum MaxAngleTSP tour, then selects the better matching formed by alternating tour edges. It handles odd and even point counts separately and runs in O(n log n).
Our algorithm
- MaxAngleTSP minimizes the sum of inner angles and has an O(n log n) optimum algorithm for odd size, while its even-size complexity remains open.The cited prior algorithm supplies the tour used by the matching method.Source: §2 · p. 3
- The algorithm constructs an optimum MaxAngleTSP tour and chooses the better matching formed by alternatingly taking and skipping tour edges.The tour-based matching is evaluated using the original Euclidean edge weights.Source: §2 · pp. 3–5
- For odd n, it tests each possible unmatched vertex; for even n, it adds an auxiliary point and compares two alternating-edge starting choices.The auxiliary point is ignored when creating the resulting matching.Source: §2 · pp. 4–5
- O(n log n) time suffices for the algorithm in both parity cases.For odd n, the tour construction takes O(n log n), followed by O(n) initial matching work and constant-time updates; the even case also takes O(n log n).Source: §2 · p. 5
3 Computational results
The evaluation tests Algorithm 1 on random square and circle instances and structured TSPLIB instances, using optimum matchings as a comparison baseline. It reports near-optimum solutions, running times, and the effect of choices in the algorithm.
3.1 Benchmark instances and test environment
- The benchmarks include uniform random points in squares and circles and structured TSPLIB instances, including mesh grids and clustered or collinear points.Square and circle instances used ten samples per size; TSPLIB instances were paired by removing the last vertex.Source: §3.1 · pp. 5–6
3.2 Evaluation layout
- Ratios are compared with optimum matching values; random-instance ratios are geometric means by type and size, while running times are arithmetic means.TSPLIB ratios and times are reported per instance, with aggregate means also reported by type across sizes.Source: §3.2 · p. 6
3.3 Test results
- For larger random square and circle instances, mean objective ratios are essentially 1; smaller instances have gaps below 2‰, with circles performing slightly better.The authors report that many larger random instances attain the optimum.Source: §3.3 · p. 7, Figure 1 · p. 8, Figure 2 · p. 8
- For larger instances, the measured optimality gaps showed no significant sensitivity to the auxiliary point’s position or the MaxAngleTSP starting point.Differences were observable only for very small instances.Source: §3.3 · p. 8
- On Euclidean TSPLIB instances with n ≤ 1084, the worst ratio was 0.9862 for fl417, a 417-vertex drilling instance with mesh-grid patterns.The tests used each instance in its original form and with its last point removed.Source: §3.3 · pp. 8–9
- Algorithm 1 takes a fraction of the blossom algorithm’s time, and Figure 4’s large square-instance tests demonstrate O(n log n) running time.The large-instance tests covered n = 1,000 to 50,000, with five instances per size.Source: §3.3 · p. 9, Figure 3 · p. 9, Figure 4 · p. 9
4 Final notes, conclusions and outlook
Algorithm 1 produced optimal or near-optimal solutions that improved with instance size, while guaranteeing O(n log n) running time. The authors conjecture asymptotic optimality, but say its proof remains under investigation.
- Solutions were optimal or near-optimal across all tested instance types, improved with size, and ran substantially faster than known optimal-solution algorithms.Source: §4 · p. 10
- Asymptotic optimality remains a conjecture; complete proofs for uniformly distributed points in a circle and the general case are under investigation.Source: §4 · p. 11
- O(n log n) running time contrasts with O(n^3) for the blossom algorithm and O(n^2.5) for Micali–Vazirani exact matching.The authors also characterize the FPTAS of Duan and Pettie as quadratic in the number of vertices.Source: §4 · p. 11
- Near-optimal performance and O(n log n) running time make the algorithm attractive for large instances where exact methods quickly become computationally prohibitive.Source: §4 · p. 11