Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching
- 1 April 1988
- journal article
- research article
- Published by Cambridge University Press (CUP) in Probability in the Engineering and Informational Sciences
- Vol. 2 (2) , 143-156
- https://doi.org/10.1017/s0269964800000711
Abstract
Given a collection of n points in the plane, the Euclidean matching problem is the task of decomposing the collection into matched pairs connected by line segments in such a way as to minimize the sum of all the segment lengths. The greedy heuristic provides an approximate solution to the Euclidean matching problem by successively matching the two closest unmatched points. We study the behavior of Gn, the sum of the lengths of the segments produced by the greedy heuristic.Keywords
This publication has 13 references indexed in Scilit:
- A survey of heuristics for the weighted matching problemNetworks, 1983
- Probabilistic analysis of divide-and-conquer heuristics for minimum weighted euclidean matchingNetworks, 1983
- Optimal Triangulation of Random Samples in the PlaneThe Annals of Probability, 1982
- On a Greedy Heuristic for Complete MatchingSIAM Journal on Computing, 1981
- Subadditive Euclidean Functionals and Nonlinear Growth in Geometric ProbabilityThe Annals of Probability, 1981
- Worst case bounds for the Euclidean matching problemComputers & Mathematics with Applications, 1981
- Decomposable searching problems I. Static-to-dynamic transformationJournal of Algorithms, 1980
- Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the PlaneMathematics of Operations Research, 1977
- Graph Theory with ApplicationsPublished by Springer Nature ,1976
- The Existence of Probability Measures with Given MarginalsThe Annals of Mathematical Statistics, 1965