On the expected value of the minimum assignment

DOI10.1002/RSA.10045MaRDI QIDQ3150198zbMATH OpenOpenAlexFDO

Authors David P. Robbins, Marshall W. Buck, Clara S. Chan

Publication date 12 March 2003

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0004175

zbMATH Keywords

minimum assignment

Mathematics Subject Classification ID

Combinatorial probability (60C05) Randomized algorithms (68W20) Discrete location and assignment (90B80)

Abstract: The minimum k-assignment of an m by n matrix X is the minimum sum of k entries of X, no two of which belong to the same row or column. If X is generated by choosing each entry independently from the exponential distribution with mean 1, then Coppersmith and Sorkin conjectured that the expected value of its minimum k-assignment is sum_{i,j ge 0, i+j<k} 1/((m-i)(n-j)) and they (with Alm) have proven this for k < 5 and in certain cases when k=5 or k=6. They were motivated by the special case of k=m=n, where the expected value was conjectured by Parisi to be sum_{i=1}^k 1/(i^2). In this paper we describe our efforts to prove the Coppersmith-Sorkin conjecture. We give evidence for the following stronger conjecture, which generalizes theirs. Conjecture. Suppose that r_1,...,r_m and c_1,...,c_n are positive real numbers. Let X be a random m by n matrix in which entry x_{ij} is chosen independently from the exponential distribution with mean 1/(r_ic_j). Then the expected value of the minimum k-assignment of X is sum_{I,J} (-1)^{k - 1 - |I| - |J|} �inom{m + n - 1 - |I| - |J|}{k - 1 - |I| - |J|}frac{1}{(sum_{i

otin I}r_i) (sum_{j

otin J} c_j)}. Here the sum is over proper subsets I of {1,...,m} and J of {1,...,n} whose cardinalities |I| and |J| satisfy |I|+|J|<k.

Recommendations

• scientific article; zbMATH DE number 1802784
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
• A proof of Parisi's conjecture on the random assignment problem
• A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment
• Certain expected values in the random assignment problem

Cited in

(16)

• The k-assignment polytope
• A proof of Parisi's conjecture on the random assignment problem
• Exploiting partial correlations in distributionally robust optimization
• Uncertain random assignment problem
• On the maximum of random assignment process
• The blind passenger and the assignment problem
• scientific article; zbMATH DE number 1802784 (Why is no real title available?)
• On assignment functions
• scientific article; zbMATH DE number 1787233 (Why is no real title available?)
• 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
• On the Maximum of a Special Random Assignment Process
• The mean field traveling salesman and related problems
• Extrema of a multinomial assignment process
• Quick or cheap? Breaking points in dynamic markets
• Random assignment problems

This page was built for publication: On the expected value of the minimum assignment

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