A survey of heuristics for the weighted matching problem

DOI10.1002/net.3230130404zbMath0532.90090OpenAlexW2024106841MaRDI QIDQ3315292

David Avis

Publication date: 1983

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230130404

zbMATH Keywords

surveyheuristicsassignment problemexact algorithmsweighted matching problemsexpected boundsabsolute boundsworst-case ratio bounds

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05) Graph theory (including graph drawing) in computer science (68R10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items (26)

On the existence of weak greedy matching heuristics ⋮ Euclidean maximum matchings in the plane -- local to global ⋮ Parallel approximation algorithms for maximum weighted matching in general graphs ⋮ New primal and dual matching heuristics ⋮ Two-way greedy: algorithms for imperfect rationality ⋮ On the use of suboptimal matchings for scaling and ordering sparse symmetric matrices ⋮ Linear-Time Approximation for Maximum Weight Matching ⋮ AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗ ⋮ Probabilistische analyse von heuristiken der kombinatorischen optimierung – ein überbllck ⋮ A quantization framework for smoothed analysis of Euclidean optimization problems ⋮ Cellular automaton decoders of topological quantum memories in the fault tolerant setting ⋮ Solving simultaneous target assignment and path planning efficiently with time-independent execution ⋮ Solving maximum weighted matching on large graphs with deep reinforcement learning ⋮ Quotient geometric crossovers and redundant encodings ⋮ New approximation results on graph matching and related problems ⋮ Almost stable matchings by truncating the Gale-Shapley algorithm ⋮ Greedy matching on a grid ⋮ A new adaptive Hungarian mating scheme in genetic algorithms ⋮ Unnamed Item ⋮ A \(2/3\)-approximation algorithm for vertex-weighted matching ⋮ Efficient Approximation Algorithms for Weighted $b$-Matching ⋮ Approximate minimum weight matching on points in k-dimensional space ⋮ Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching ⋮ On computing the diameter of a point set in high dimensional Euclidean space. ⋮ An analysis of a decomposition heuristic for the assignment problem ⋮ A lower bound to the complexity of Euclidean and rectilinear matching algorithms

Cites Work

• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• On Approximation Methods for the Assignment Problem
• Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching
• Paths, Trees, and Flowers
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A survey of heuristics for the weighted matching problem