A Generalization of the Random Assignment Problem

MaRDI QIDQ6470472zbMATH OpenFDO

Authors Svante Linusson, Johan Wästlund

Publication date 20 June 2000

Abstract: 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=noinfty$, 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 $p{i}^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 $kleq5$. We have used the same computer program to verify this conjecture also for k=6.

This page was built for publication: A Generalization of the Random Assignment Problem

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