Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-23T09:56:01.216Z Has data issue: false hasContentIssue false
  • English
  • Français

Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching

Published online by Cambridge University Press:  27 July 2009

David Avis ,
Burgess Davis  and
J. Michael Steele
David Avis
Affiliation:
School of Computer Science McGill University, Montré, Québec H3A 2K6, Canada
Burgess Davis
Affiliation:
Department of Mathematics and Statistics Purdue University, West Lafayette, Indiana 47907
J. Michael Steele
Affiliation:
Program in Statistics and Opertions Research Princeton University, Princeton, New Jersey 08544
Get access Rights & Permissions [Opens in a new window]

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.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 2 , Issue 2 , April 1988 , pp. 143 - 156
Copyright
Copyright © Cambridge University Press 1988

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Avis, D. (1981). Worst case bounds for the Euclidean matching problem. Computers and Mathematical Applications 7:251–257.CrossRefGoogle Scholar
Avis, D. (1983). A survey of heuristics for the weighted matching problem. Networks 13:475–493.CrossRefGoogle Scholar
Beardwood, J., Halton, J.H., & Hammersley, J.M. (1959). The shortest path through many points. Proceedings of the Cambridge Philosophical Society 55:299–327.CrossRefGoogle Scholar
Bentley, J.L. & Saxe, J.B. (1980). Decomposable searching problems 1: static to dynamic transformations. Journal of Algorithms 1:301–358.CrossRefGoogle Scholar
Bondy, J.A. & Murty, U.S.R. (1976). Graph Theory with Applications. New York: American Elsevier Publishing Co., Inc.CrossRefGoogle Scholar
Few, L. (1955). The shortest road through n points in a region. Mathematika 2, 141–144.CrossRefGoogle Scholar
Iri, M., Murota, K., & Matsui, S. (1981). Linear time heuristics for the minimum weight perfect matching problem on a plane. Information Proceedings Letters 12:206–209.CrossRefGoogle Scholar
Karp, R.M. (1977). Probabilistics analysis of partitioning algorithms for the traveling salesman problem in the plane. Mathematics of Operations Research 2:209–224.CrossRefGoogle Scholar
Karp, R.M. & Steele, J.M. (1985). Probabilistic analysis of heuristics. In Lawler, E.L. et al. (eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. NY: John Wiley and Sons, pp. 181–206.Google Scholar
Papadimitriou, C.H. & Steiglitz, K. (1982). Combinatorial Optimization: Algorithms and Complexity. Englewood Cliffs, NJ: Prentice-Hall.Google Scholar
Papadimitriou, C.H. (1977). The probabilistic analysis of matching heuristics. Proceedings of the 15 Allerton Conference on Communication Control and Computing, pp. 368–378.Google Scholar
Reingold, E.M. & Supowit, K.J. (1983). Probabilistic analysis of divide and conquer heuristics for minimum weighted Euclidean matchings. Networks 13:49–66.CrossRefGoogle Scholar
Reingold, E.M. & Tarjan, R.E. (1981). On a greedy heuristic for complete matching. SIAM Journal of Computing 10:676–681.CrossRefGoogle Scholar
Steele, J.M. (1981). Subadditive Euclidean functionals and nonlinear growth in geometric probability. Annals of Probability 9:365–376.CrossRefGoogle Scholar
Steele, J.M. (1982). Optimal triangulation of random samples in the plane. Annals of Probability 10:548–553.CrossRefGoogle Scholar
Strassen, V. (1965). The existence of probability measures with given marginals. Annals of Mathematical Statistics 36:423–439.CrossRefGoogle Scholar