On random quadratic bottleneck assignment problems

Publikation: Beitrag in einer FachzeitschriftArtikelBegutachtung

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.
Originalspracheenglisch
Seiten (von - bis)227-232
FachzeitschriftMathematical Programming
Jahrgang23
Ausgabenummer1
DOIs
PublikationsstatusVeröffentlicht - 1982

Fingerprint

Untersuchen Sie die Forschungsthemen von „On random quadratic bottleneck assignment problems“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren