Constructive bounds and exact expectations for the random assignment problem

DOI<113::AID-RSA1>3.0.CO;2-S 10.1002/(SICI)1098-2418(199909)15:2<113::AID-RSA1>3.0.CO;2-SzbMath0957.90076MaRDI 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 physics; bipartite matching; weighted matching

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

90B80: Discrete location and assignment

Related Items

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

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