Algorithm and Average-value Bounds for Assignment Problems
Wilm E. Donath · IBM Journal of Research and Development · 1969
A new suboptimal intermediate-speed algorithm which uses n2ln n steps is developed for the assignment problem. Upper and lower bounds are derived, using this algorithm and other methods, for the average values of three classes of n × n assignment problems: 1. When the elements of the matrix are random numbers uniformly distributed over the range 0 to 1, the average optimal value is smaller than 2.37 and larger than 1 for problems with large n. Experimentally the value is about 1.6. 2. When the elements of the matrix are random numbers such that the probability of being less than x is xk+1(k ≠ 0), asymptotic express ions for the upper and lower bounds of the average optimal value are Cknk/(k+1)and Ck[(k + 1)/k]nk/(k+1), respectively. 3. When each column of the matrix is a random permutation of the integers 1 to n, asymptotic upper and lower bounds are 2.37n and 1.54n, respectively. Experimentally the value is about 1.8n.