On the Expected Value of a Random Assignment Problem
Author:
- David W. WalkupDWDavid W. Walkup
- 1 August 1979
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 8 (3) , 440-442
Abstract
Given an n by n matrix X, the assignment problem asks for a set of n entries, one from each column and row, with the minimum sum. It is shown that the expected value of this minimum sum is less than 3, independent of n, if X consists of independent random variables uniformly distributed from 0 to 1.Keywords
This publication has 3 references indexed in Scilit:
- Matchings in random regular bipartite digraphsDiscrete Mathematics, 1980
- Algorithm and Average-value Bounds for Assignment ProblemsIBM Journal of Research and Development, 1969
- On Approximation Methods for the Assignment ProblemJournal of the ACM, 1962