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-SMaRDI QIDQ4265785zbMATH OpenOpenAlexFDO

Authors Don Coppersmith, Gregory B. Sorkin

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)

Recommendations

• scientific article; zbMATH DE number 1787233
• An easy proof of the \(\zeta (2)\) limit in the random assignment problem
• Certain expected values in the random assignment problem

Cites work

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

Cited in

(35)

• Random matching problems on the complete graph
• On the Maximum of a Special Random Assignment Process
• On the expected optimal value of random assignment problems: Experimental results and open questions
• Weight of a link in a shortest path tree and the Dedekind eta function
• Asymptotic properties of random multidimensional assignment problems
• Random assignment and shortest path problems
• Minimum cost matching in a random graph with random costs
• An asymptotical study of combinatorial optimization problems by means of statistical mechanics
• scientific article; zbMATH DE number 1833413 (Why is no real title available?)
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
• An easy proof of the \(\zeta (2)\) limit in the random assignment problem
• Optimality of belief propagation for random assignment problem
• scientific article; zbMATH DE number 1802784 (Why is no real title available?)
• The \(\zeta(2)\) limit in the random assignment problem
• The blind passenger and the assignment problem
• The mean field traveling salesman and related problems
• Asymptotic results for random multidimensional assignment problems
• The Probabilistic Analysis of a Heuristic for the Assignment Problem
• Efficient algorithms for three‐dimensional axial and planar random assignment problems
• A two-objective fuzzy \(k\)-cardinality assignment problem
• Asymptotics in the random assignment problem
• Typical values of extremal-weight combinatorial structures with independent symmetric weights
• A proof of Parisi's conjecture on the random assignment problem
• Random assignment problems
• Extrema of a multinomial assignment process
• Asymptotic moments of the bottleneck assignment problem
• Random Assignment with Integer Costs
• The random fractional matching problem
• The Dyck bound in the concave 1-dimensional random assignment model
• The \(k\)-assignment polytope
• ON THE FLUCTUATION IN THE RANDOM ASSIGNMENT PROBLEM
• On the maximum of random assignment process
• Certain expected values in the random assignment problem
• Belief propagation: an asymptotically optimal algorithm for the random assignment problem
• A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment

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)