Asymptotic properties of the quadratic assignment problem

J.B.G. Frenk, M. Houweninge, van, A.H.G. Rinnooy Kan

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

For the general quadratic assignment problem as well as for a planar version of this problem, we extend earlier work by Burkard and Fincke to prove that the ratio of the maximal to the minimal solution value converges to 1 almost surely. In fact, any solution value can almost surely be written asymptotically as a simple, explicitly given function of the problem size. Theoretical analysis and computational experiments reveal the convergence to be relatively fast.
Original languageEnglish
Pages (from-to)100-116
Number of pages17
JournalMathematics of Operations Research
Volume10
Issue number1
DOIs
Publication statusPublished - 1985

Fingerprint Dive into the research topics of 'Asymptotic properties of the quadratic assignment problem'. Together they form a unique fingerprint.

Cite this