A Lower Bound on the Expected Cost of an Optimal Assignment

DOI10.1287/MOOR.18.2.267MaRDI QIDQ5287981zbMATH OpenOpenAlexFDO

Authors Michel X. Goemans, Muralidharan S. Kodialam

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

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

Recommendations

• scientific article; zbMATH DE number 4043612
• Certain expected values in the random assignment problem
• Constructive bounds and exact expectations for the random assignment problem
• The random linear bottleneck assignment problem

Cited in

(13)

• Anomalous scaling of the optimal cost in the one-dimensional random assignment problem
• Exploiting partial correlations in distributionally robust optimization
• scientific article; zbMATH DE number 4043612 (Why is no real title available?)
• Constructive bounds and exact expectations for the random assignment problem
• Certain expected values in the random assignment problem
• A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment
• Asymptotics in the random assignment problem
• Random assignment problems
• On the expected optimal value of random assignment problems: Experimental results and open questions
• Asymptotic behavior of the expected optimal value of the multidimensional assignment problem
• The \(\zeta(2)\) limit in the random assignment problem
• The planted matching problem: phase transitions and exact results
• scientific article; zbMATH DE number 1787233 (Why is no real title available?)

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

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