Stochastic Analysis of the Quadratic Assignment Problem

Let A and B be m × m matrices. The aim is to maximize Q(σ) = ∑_{i, j}a_ijb_σ(i)σ(j) over all permutations σ of 1, 2, …, m. We define a simple “greedy” algorithm that constructs a permutation σ* that gives a large Q(σ*). Assuming that the entries of A are i.i.d. with a symmetric distribution, and that the entries of B are independent of A, we show under some weak moment conditions EQ(σ*) ≥ K⁻¹m^3/2(log m)^1/2, where the constant k does not depend on m. This contrasts with the fact that max_σ ≤ Km^3/2(log m)^1/2 with overwhelming probability.