Fast Approximation Algorithms for Euclidean Minimum Weight Perfect Matching

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 dep…