Approximating the maximum quadratic assignment problem

In the maximum quadratic assignment problem three n×n nonnegative symmetric matrices A = (a_ij), B = (b_ij), and C = (c_ij) are given and the objective is to compute a permutation π of V = {1, ..., n} so that ∑a_π(i),π(j)b_i,j(for i,j∈V and i is not equal to j) +∑c_i,π(i)(for i∈V) is maximized. An approximation algorithm with a constant performance guarantee, 1/4 , under the assumption that the weights in B satisfy the triangle inequality (TI) b_i,j≤b_i,k+b_k,j, for all i, j, k∈V. For maximum linear arrangement the bound guaranteed by the proposed algorithm is 1/2 , which slightly improves from the recent results.