On random quadratic bottleneck assignment problems

The relative error between best and worst solution of quadratic bottleneck assignment problems with cost coefficients dijpq =aipbjq is considered, where aip is either arbitrarily given or corresponds to a distance in the plane. It is shown that the relative error is bounded by a function ∈(m), tending to zero, with probability tending to one as m → ∞, 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.