Approximating the Minimum Quadratic Assignment Problems

We consider the well-known minimum quadratic assignment problem. In this problem we are given two n x n nonnegative symmetric matrices A = (a(ij)) and B = (b(ij)). The objective is to compute a permutation pi of V = {1, ... , n} so that Sigma(i,j is an element of V)(i not equal j) a(pi(i),pi(j))b(i,j) is minimized. We assume that A is a 0/1 incidence matrix of a graph, and that B satisfies the triangle inequality. We analyze the approximability of this class of problems by providing polynomial bounded approximations for some special cases, and inapproximability results for other cases.