A linear n × n assignment problem is considered for which the elements of the cost matrix are sampled from a continuous probability distribution. Based on the zero entries of the reduced matrix the expectation of the maximum number of initial assignments is determined for general n, as well as an asymptotic value for large n.
- occupancy problem
- Bipartite graph
- Linear assignment problem
Nawijn, W. M., & Dorhout, B. (1989). On the expected number of assignments in reduced matrices for the linear assignment problem. Operations research letters, 8(6), 329-335. https://doi.org/10.1016/0167-6377(89)90018-7