Constructive bounds and exact expectations for the random assignment problem

DOI<link itemprop=identifier href="https://doi.org/10.1002/(SICI)1098-2418(199909)15:2<113::AID-RSA1>3.0.CO;2-S" /><113::AID-RSA1>3.0.CO;2-S 10.1002/(SICI)1098-2418(199909)15:2<113::AID-RSA1>3.0.CO;2-SzbMath0957.90076OpenAlexW2028955990MaRDI QIDQ4265785

Gregory B. Sorkin, Don Coppersmith

Publication date: 22 September 1999

Full work available at URL: https://doi.org/10.1002/(sici)1098-2418(199909)15:2<113::aid-rsa1>3.0.co;2-s

zbMATH Keywords

statistical physicsbipartite matchingweighted matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Discrete location and assignment (90B80)

Related Items (17)

Asymptotic properties of random multidimensional assignment problems ⋮ On the Maximum of a Special Random Assignment Process ⋮ On the maximum of random assignment process ⋮ The mean field traveling salesman and related problems ⋮ Extrema of a multinomial assignment process ⋮ A two-objective fuzzy \(k\)-cardinality assignment problem ⋮ The Blind Passenger and the Assignment Problem ⋮ The ?(2) limit in the random assignment problem ⋮ Random assignment problems ⋮ Efficient algorithms for three‐dimensional axial and planar random assignment problems ⋮ A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment ⋮ Weight of a link in a shortest path tree and the Dedekind Eta function ⋮ The \(k\)-assignment polytope ⋮ An asymptotical study of combinatorial optimization problems by means of statistical mechanics ⋮ The Dyck bound in the concave 1-dimensional random assignment model ⋮ Typical values of extremal-weight combinatorial structures with independent symmetric weights ⋮ Asymptotic results for random multidimensional assignment problems

Cites Work

• Unnamed Item
• 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
• On the Expected Value of a Random Assignment Problem
• On linear programs with random costs
• On Approximation Methods for the Assignment Problem
• Average Case Analysis of a Heuristic for the Assignment Problem
• A Lower Bound on the Expected Cost of an Optimal Assignment
• Algorithm and Average-value Bounds for Assignment Problems
• A Combinatorial Algorithm

This page was built for publication: Constructive bounds and exact expectations for the random assignment problem