Fast Approximation Algorithms for Euclidean Minimum Weight Perfect Matching
Stefan Hougardy, Karolina Tammemaa · Theory of Computing Systems · 2026
Abstract We study the Euclidean minimum weight perfect matching problem for n points in the plane. It is known that any deterministic approximation algorithm whose approximation ratio depends only on n requires at least $$\Omega (n \log n)$$ Ω ( n log n ) time. We propose such an algorithm for the Euclidean minimum weight perfect matching problem with runtime $$O(n\log n)$$ O ( n log n ) and show that it has approximation ratio $$O(n^{0.206})$$ O ( n 0.206 ) . This improves the so far best known approximation ratio of n /2. We also develop an $$O(n \log n)$$ O ( n log n ) algorithm for the Euclidean minimum weight perfect matching problem in higher dimensions and show it has approximation ratio $$O(n^{0.412})$$ O ( n 0.412 ) in all fixed dimensions.