A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment
From MaRDI portal
Publication:4667865
DOI10.1002/rsa.20066zbMath1090.90127OpenAlexW2529617700WikidataQ122981843 ScholiaQ122981843MaRDI QIDQ4667865
Publication date: 21 April 2005
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20066
Combinatorial probability (60C05) Discrete location and assignment (90B80) Randomized algorithms (68W20)
Related Items
A lower bound on the expected optimal value of certain random linear programs and application to shortest paths in directed acyclic graphs and reliability ⋮ The mean field traveling salesman and related problems ⋮ Unnamed Item ⋮ Exploiting partial correlations in distributionally robust optimization ⋮ The Blind Passenger and the Assignment Problem ⋮ Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs ⋮ Random assignment problems ⋮ The planted matching problem: phase transitions and exact results ⋮ The minimum perfect matching in pseudo-dimension 0 < q < 1 ⋮ A general method for lower bounds on fluctuations of random variables
Cites Work
- Unnamed Item
- Certain expected values in the random assignment problem
- A proof of Parisi's conjecture on the random assignment problem
- The ?(2) limit in the random assignment problem
- On the Expected Value of a Random Assignment Problem
- On the expected value of the minimum assignment
- Constructive bounds and exact expectations for the random assignment problem
- A Lower Bound on the Expected Cost of an Optimal Assignment
