Fast Approximation Algorithms for Euclidean Minimum Weight Perfect Matching
<|reference_start|>Fast Approximation Algorithms for Euclidean Minimum Weight Perfect Matching: 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.2995})$. 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.599})$ in all fixed dimensions.<|reference_end|>
@article{hougardy2024fast,
    title={Fast Approximation Algorithms for Euclidean Minimum Weight Perfect
  Matching},
    author={Stefan Hougardy and Karolina Tammemaa},
    journal={arXiv preprint arXiv:2407.07749},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.07749},
    primaryClass={cs.CG cs.DS math.CO}
}