Constructive bounds and exact expectations for the random assignment problem
From MaRDI portal
Publication:4265785
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.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
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
