Average Case Analysis of a Heuristic for the Assignment Problem

DOI10.1287/MOOR.19.3.513MaRDI QIDQ4316542zbMATH OpenOpenAlexFDO

Authors Alexander H. G. Rinnooy Kan, Richard Karp, Rakesh V. Vohra

Publication date 11 December 1994

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.19.3.513

zbMATH Keywords

heuristicperfect matchingexpected weight of the assignmentrandom 2-out bipartite graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• The Probabilistic Analysis of a Heuristic for the Assignment Problem
• Constructive bounds and exact expectations for the random assignment problem
• Average-case analysis of algorithms for matchings and related problems
• Matching algorithms are fast in sparse random graphs

Cited in

(11)

• An analysis of a decomposition heuristic for the assignment problem
• An average case analysis of the minimum spanning tree heuristic for the power assignment problem
• Existence of a perfect matching in a random (\(1+e^{-1}\))-out bipartite graph
• Selected topics on assignment problems
• Constructive bounds and exact expectations for the random assignment problem
• The ``largest element first heuristic for the maximization assignment problem
• scientific article; zbMATH DE number 7651215 (Why is no real title available?)
• Optimality of belief propagation for random assignment problem
• The Probabilistic Analysis of a Heuristic for the Assignment Problem
• Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis
• scientific article; zbMATH DE number 1496581 (Why is no real title available?)

This page was built for publication: Average Case Analysis of a Heuristic for the Assignment Problem

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