2000/06/20 by Svante Linusson, Linusson, Svante, Johan Waestlund +1 · 1 citation
Computer Science · Economics, Econometrics and Finance · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Constraint Satisfaction and Optimization #FOS: Mathematics #Game Theory and Voting Systems #Probability (math.PR) #math.CO #math.PR
paper · pdf · doi:10.48550/arxiv.math/0006146
40 pages, 3 figures
arxiv created 2000/06/20 · openalex publication_date 2000/06/20 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give a conjecture for the expected value of the optimal k-assignment in an m x n-matrix, where the entries are all exp(1)-distributed random variables or zeros. We prove this conjecture in the case there is a zero-cost k-1-assignment. Assuming our conjecture, we determine some limits, as k=m=n→ ∞, of the expected cost of an optimal n -assignment in an n x n-matrix with zeros in some region. If we take the region outside a quarter-circle inscribed in the square matrix, this limit is thus conjectured to be π2/24. We give a computer-generated verification of a conjecture of Parisi for k=m=n=7 and of a conjecture of Coppersmith and Sorkin for k≤ 5. We have used the same computer program to verify this conjecture also for k=6.