Fast Approximation Algorithms for Euclidean Minimum Weight Perfect Matching
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914240489586688 |
|---|---|
| author | Hougardy, Stefan Tammemaa, Karolina |
| author_facet | Hougardy, Stefan Tammemaa, Karolina |
| contents | 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 $Ω(n \log n)$ time. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_07749 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast Approximation Algorithms for Euclidean Minimum Weight Perfect Matching Hougardy, Stefan Tammemaa, Karolina Computational Geometry Data Structures and Algorithms Combinatorics 68R10 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 $Ω(n \log n)$ time. 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. |
| title | Fast Approximation Algorithms for Euclidean Minimum Weight Perfect Matching |
| topic | Computational Geometry Data Structures and Algorithms Combinatorics 68R10 |
| url | https://arxiv.org/abs/2407.07749 |