Fast Approximation Algorithms for Euclidean Minimum Weight Perfect Matching
Abstract
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.
Fields of Study & Subjects
Algorithms and Data Compression
Machine Learning and Algorithms
Optimization and Search Problems
Publication details
- Journal / source
- Theory of Computing Systems
- Publisher
- Springer Science and Business Media LLC
- Volume
- 70
- Issue
- 2
- Publication date
- 8 April 2026
- Language
- EN