Fast approximation algorithms for Euclidean minimum weight perfect matching

DOI10.1007/978-3-031-81396-2_6MaRDI QIDQ6974418zbMATH OpenFDO

Authors Stefan Hougardy, Karolina Tammemaa

Publication date 6 June 2025

Full work available at URL https://doi.org/10.1007/978-3-031-81396-2_6

zbMATH Keywords

approximation algorithmseuclidean matching

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Cites work

• A divide-and-conquer algorithm for min-cost perfect matching in the plane
• A lower bound for approximating the geometric minimum weight matching
• An O(n log n) algorithm for the all-nearest-neighbors problem
• Approximate minimum weight matching on points in k-dimensional space
• Geometry Helps in Matching
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 1305475 (Why is no real title available?)
• Maximum matching and a polyhedron with 0,1-vertices
• On the possibility, to travel around a graph without repetition and without cutting
• Paths, Trees, and Flowers
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems

Cited in

(1)

• Fast approximation algorithms for Euclidean minimum weight perfect matching

This page was built for publication: Fast approximation algorithms for Euclidean minimum weight perfect matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6974418)