A Generalization of the Random Assignment Problem

Svante Linusson, Johan Waestlund

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 co…