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

dual heuristic algorithmlower boundoptimal assignment

Mathematics Subject Classification ID

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

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)

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

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)