Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching

DOI10.1017/S0269964800000711zbMath1134.90468MaRDI QIDQ3415878

J. Michael Steele, Burgess Davis, David Avis

Publication date: 19 January 2007

Published in: Probability in the Engineering and Informational Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Related Items

Poisson matching, Probabilistische analyse von heuristiken der kombinatorischen optimierung – ein überbllck, Probabilistic analysis of optimization problems on sparse random shortest path metrics, Random shortest paths: non-Euclidean instances for metric optimization problems, On the consistency of the crossmatch test

Cites Work

• Unnamed Item
• Worst case bounds for the Euclidean matching problem
• Linear-time approximation algorithms for finding the minimum-weight perfect matching on a plane
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• Optimal triangulation of random samples in the plane
• A survey of heuristics for the weighted matching problem
• Decomposable searching problems I. Static-to-dynamic transformation
• On a Greedy Heuristic for Complete Matching
• Probabilistic analysis of divide‐and‐conquer heuristics for minimum weighted euclidean matching
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• The Existence of Probability Measures with Given Marginals