Average Case Analysis of a Heuristic for the Assignment Problem

DOI10.1287/moor.19.3.513zbMath0813.90122OpenAlexW2016806092MaRDI QIDQ4316542

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

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)

Related Items

Unnamed Item ⋮ Existence of a perfect matching in a random (\(1+e^{-1}\))-out bipartite graph ⋮ Unnamed Item ⋮ Selected topics on assignment problems ⋮ Constructive bounds and exact expectations for the random assignment problem