Approximating the minimum quadratic assignment problems

Abstract

We consider the well-known minimum quadratic assignment problem. In this problem we are given two n × n nonnegative symmetric matrices A = ( a _ij ) and B = ( b _ij ). The objective is to compute a permutation π of V = {1,…, n } so that ∑ i , j ∈ V _{i ≠ j} a _{π( i ),π( 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.