ON RANDOM QUADRATIC BOTTLENECK ASSIGNMENT PROBLEMS

The relative error between best and worst solution of quadratic bottleneck assignment problems with cost coefficients d//i//j//p//q equals a//i//pb//j//q is considered, where a//i//p is either arbitrarily given or corresponds to a distance in the plane. It is shown that the relative error is bounded by a function epsilon (m), tending to zero, with probability tending to one as m approaches infinity , provided the data are uniformly distributed. This implies that any algorithm for the above mentioned problems yields asymptotically an arbitrarily small relative error with probability tending to one.