Fast approximation algorithms for Euclidean minimum weight perfect matching

Publikationstyp
Journal Article
Date Issued
2026-06-01
Sprache
English
Author(s)
Hougardy, Stefan  
Tammemaa, Karolina  
Algorithmen und Komplexität E-11  
TORE-DOI
10.15480/882.17028
TORE-URI
https://hdl.handle.net/11420/62869
Journal
Theory of computing systems  
Volume
70
Issue
2
Article Number
25
Citation
Theory of Computing Systems 70 (2): 25 (2026)
Publisher DOI
10.1007/s00224-025-10254-7
Scopus ID
2-s2.0-105035821426
Publisher
Springer
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 Ω(nlogn) time. We propose such an algorithm for the Euclidean minimum weight perfect matching problem with runtime O(nlogn) and show that it has approximation ratio O(n0.206). This improves the so far best known approximation ratio of n/2. We also develop an O(nlogn) algorithm for the Euclidean minimum weight perfect matching problem in higher dimensions and show it has approximation ratio O(n0.412) in all fixed dimensions.
Subjects
Approximation algorithms
Euclidean matching
DDC Class
510: Mathematics
Lizenz
https://creativecommons.org/licenses/by/4.0/
Publication version
publishedVersion
Loading...
Thumbnail Image
Name

s00224-025-10254-7.pdf

Type

Main Article

Size

443.4 KB

Format

Adobe PDF