A Lower Bound on the Expected Cost of an Optimal Assignment

DOI10.1287/moor.18.2.267zbMath0779.90066OpenAlexW2142946851MaRDI QIDQ5287981

Muralidharan S. Kodialam, Michel X. Goemans

Publication date: 5 August 1993

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

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

zbMATH Keywords

lower boundoptimal assignmentdual heuristic algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Linear programming (90C05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (8)

Asymptotic behavior of the expected optimal value of the multidimensional assignment problem ⋮ Exploiting partial correlations in distributionally robust optimization ⋮ The ?(2) limit in the random assignment problem ⋮ Random assignment problems ⋮ Asymptotics in the random assignment problem ⋮ A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment ⋮ Constructive bounds and exact expectations for the random assignment problem ⋮ The planted matching problem: phase transitions and exact results

This page was built for publication: A Lower Bound on the Expected Cost of an Optimal Assignment