On the Maximum Quadratic Assignment Problem

Quadratic Assignment is a basic problem in combinatorial optimization, which generalizes several other problems such as Traveling Salesman, Linear Arrangement, Dense k Subgraph, and Clustering with given sizes. The input to the Quadratic Assignment Problem consists of two n x n symmetric non-negative matrices W = (w(i,j)) and D = (d(i,j)). Given matrices W, D, and a permutation pi : [n] -> [n], the objective function is Q(pi) (=)over dot Sigma(i, j is an element of[n],i not equal j) W-i,W-j d(pi(i),pi(j)). In this paper, we study the Maximum Quadratic Assignment Problem, where the goal is to find a permutation it that maximizes Q(pi). We give an (O) over tilde(root n) approximation algorithm, which is the first non-trivial approximation guarantee for this problem. The above guarantee also holds when the matrices W, D are asymmetric. An indication of the hardness of Maximum Quadratic Assignment is that it contains as a special case, the Dense k Subgraph problem, for which the best known approximation ratio approximate to n(1/3) (Feige et al. [8]). When one of the matrices W,D satisfies triangle inequality, we obtain a 2e/e-1 approximate to 3.16 approximation algorithm. This improves over the previously best-known approximation guarantee of 4 (Arkin et al. [4]) for this special case of Maximum Quadratic Assignment. The performance guarantee for Maximum Quadratic Assignment with triangle inequality can be proved relative to an optimal solution of a natural linear programming relaxation, that has been used earlier in Branch-and-Bound approaches (see eg. Adams and Johnson [1]). It can also be shown that this LP has an integrality gap of (Omega) over tilde(root n) for general Maximum Quadratic Assignment.