我们研究了在平面内对$n$个点求解欧氏最小权完美匹配的问题。已知该问题的确定性近似算法必须至少具有$\Omega(n \log n)$的时间复杂度。我们提出了一种时间复杂度为$O(n\log n)$的欧氏最小权完美匹配问题的近似算法，并证明其近似比为$O(n^{0.206})$，改进了目前最佳的近似比$n/2$。此外，我们还开发了固定维度下高维空间中的一个$O(n \log n)$时间复杂度的算法，并证明其在所有固定维度下的近似比为$O(n^{0.412})$。

We study the problem of finding a Euclidean minimum weight perfect matching for $n$ points in the plane. It is known that a deterministic approximation algorithm for this problems must have at least $\Omega(n \log n)$ runtime. We propose such an algorithm for the Euclidean minimum weight perfect matching problem with runtime $O(n\log n)$ and show that it has approximation ratio $O(n^{0.206})$. This improves the so far best known approximation ratio of $n/2$. We also develop an $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})$ in all fixed dimensions.