Constructive bounds and exact expectations for the random assignment problem

DOI10.1002/(SICI)1098-2418(199909)15:2%3C113::AID-RSA1%3E3.0.CO;2-SzbMATH Open0957.90076OpenAlexW2028955990MaRDI QIDQ4265785FDOQ4265785

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%3C113::aid-rsa1%3E3.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)

Cites Work

• Title not available (Why is that?)
• On linear programs with random costs
• Asymptotics in the random assignment problem
• On Approximation Methods for the Assignment Problem
• On the expected optimal value of random assignment problems: Experimental results and open questions
• On the Expected Value of a Random Assignment Problem
• A Combinatorial Algorithm
• Certain expected values in the random assignment problem
• Average Case Analysis of a Heuristic for the Assignment Problem
• Algorithm and Average-value Bounds for Assignment Problems
• A Lower Bound on the Expected Cost of an Optimal Assignment

Cited In (22)

• The Blind Passenger and the Assignment Problem
• Weight of a link in a shortest path tree and the Dedekind Eta function
• The Dyck bound in the concave 1-dimensional random assignment model
• Typical values of extremal-weight combinatorial structures with independent symmetric weights
• Asymptotic properties of random multidimensional assignment problems
• On the maximum of random assignment process
• 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
• The mean field traveling salesman and related problems
• On the Maximum of a Special Random Assignment Process
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
• An easy proof of the \(\zeta (2)\) limit in the random assignment problem
• The \(k\)-assignment polytope
• Asymptotics in the random assignment problem
• Random assignment problems
• On the expected optimal value of random assignment problems: Experimental results and open questions
• An asymptotical study of combinatorial optimization problems by means of statistical mechanics
• Extrema of a multinomial assignment process
• The \(\zeta(2)\) limit in the random assignment problem
• A two-objective fuzzy \(k\)-cardinality assignment problem
• Efficient algorithms for three‐dimensional axial and planar random assignment problems
• Asymptotic results for random multidimensional assignment problems

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

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