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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\Omega (n \log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time. We propose such an algorithm for the Euclidean minimum weight perfect matching problem with runtime <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$O(n\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and show that it has approximation ratio <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$O(n^{0.206})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow> <mn>0.206</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. This improves the so far best known approximation ratio of n/2. We also develop an <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$O(n \log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> algorithm for the Euclidean minimum weight perfect matching problem in higher dimensions and show it has approximation ratio <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$O(n^{0.412})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow> <mn>0.412</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> in all fixed dimensions.

Fast Approximation Algorithms for Euclidean Minimum Weight Perfect Matching

期刊论文
出版模式：

开放获取
发表日期：

2026年4月8日

查看全文

Stefan Hougardy,
Karolina Tammemaa

摘要

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.