A partitioning algorithm for minimum weighted Euclidean matching

DOI10.1016/0020-0190(84)90024-3MaRDI QIDQ794175zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Martin Dyer, Alan Frieze

Publication date 1984

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(84)90024-3

zbMATH Keywords

minimal weighted Euclidean matchingprobabilistic analysis of algorithms

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An efficient heuristic algorithm for minimum matching
• Simulated annealing algorithm for the minimum weighted perfect euclidean matching problem
• Partitioning heuristics for two geometric maximization problems
• On the weighted Euclidean matching problem in R^d
• scientific article; zbMATH DE number 1855663
• Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching
• On the Euclidean assignment problem
• Average-case approximation ratio of the 2-opt algorithm for the TSP
• Probabilistische analyse von heuristiken der kombinatorischen optimierung – ein überbllck

Cites work

• A Fast Algorithm for the Euclidean Traveling Salesman Problem, Optimal with Probability One
• Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching
• Maximum matching and a polyhedron with 0,1-vertices
• On a Greedy Heuristic for Complete Matching
• Paths, Trees, and Flowers
• 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
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• The Travelling Salesman Problem and Minimum Matching in the Unit Square
• Worst case bounds for the Euclidean matching problem

Cited in

(17)

• A lower bound to the complexity of Euclidean and rectilinear matching algorithms
• On the Euclidean assignment problem
• Quantizers ad the worst case Euclidean traveling salesman problem
• Heuristic methods and applications: A categorized survey
• Smoothed analysis of partitioning algorithms for Euclidean functionals
• Minimum-error classes for matching parts
• scientific article; zbMATH DE number 992001 (Why is no real title available?)
• An efficient heuristic algorithm for minimum matching
• A survey of heuristics for the weighted matching problem
• Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching
• A Monte Carlo solution to the minimal Euclidean matching
• scientific article; zbMATH DE number 1202983 (Why is no real title available?)
• On the weighted Euclidean matching problem in R^d
• Simulated annealing algorithm for the minimum weighted perfect euclidean matching problem
• Randomized algorithms for the on-line minimum matching problem on euclidean space
• Equitable connected partition and structural parameters revisited: N-fold beats Lenstra
• Partitioning heuristics for two geometric maximization problems

This page was built for publication: A partitioning algorithm for minimum weighted Euclidean matching

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