Abstract
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.
Originalsprache | englisch |
---|---|
Seiten (von - bis) | 227-232 |
Fachzeitschrift | Mathematical Programming |
Jahrgang | 23 |
Ausgabenummer | 1 |
DOIs | |
Publikationsstatus | Veröffentlicht - 1982 |