On random quadratic bottleneck assignment problems

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish
Pages (from-to)227-232
JournalMathematical Programming
Issue number1
Publication statusPublished - 1982

Cite this