Asymptotic Properties of the Quadratic Assignment Problem

Source 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.