Quadratic assignment is a basic problem in combinatorial optimization that 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 nonnegative matrices 
and 
. Given matrices W, D, and a permutation 
, the objective function is 
. In this paper, we study the maximum quadratic assignment problem, where the goal is to find a permutation 
that maximizes 
. We give an 
-approximation algorithm, which is the first nontrivial 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 is 
(Feige et al. [Feige, U., G. Kortsarz, D. Peleg. 2001. The dense k-subgraph problem. Algorithmica 29(3) 410–421]).
When one of the matrices W, D satisfies triangle inequality, we obtain a 
-approximation algorithm. This improves over the previously best-known approximation guarantee of four (Arkin et al. [Arkin, E. M., R. Hassin, M. Sviridenko. 2001. Approximating the maximum quadratic assignment problem. Inform. Processing Lett. 77 13–16]) 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 [Adams, W. P., T. A. Johnson. 1994. Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 16 43–77]). It can also be shown that this linear program (LP) has an integrality gap of 
for general maximum quadratic assignment.
