On the maximum quadratic assignment problem

Abstract

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 × n symmetric nonnegative matrices W = (wi,j) and D = (di,j). Given matrices W, D, and a permutation π: [n] → [n], the objective function is Q(π) :=σi,j∈[n],i≠j wi,j d π(i)π(j) In this paper, we study the maximum quadratic assignment problem, where the goal is to find a permutation π that maximizes Q(π).Wegivean Õ(√n)-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 ≈n1/3 (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 2e/(e - 1) ≈ 3.16-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 ω̃(√n) for general maximum quadratic assignment. © 2009 INFORMS.