A survey of heuristics for the weighted matching problem

DOI10.1002/net.3230130404zbMath0532.90090MaRDI 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

survey; heuristics; assignment problem; exact algorithms; weighted matching problems; expected bounds; absolute bounds; worst-case ratio bounds

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

05C35: Extremal problems in graph theory

65K05: Numerical mathematical programming methods

68R10: Graph theory (including graph drawing) in computer science

90C08: Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)

90-02: Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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