About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SODA 2009
Conference paper
On the maximum quadratic assignment problem
Abstract
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 = (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(π). We give an Õ(√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 ≈ n 1/3 (Feige et al. [8]). 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 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 Ω̄(√n) for general Maximum Quadratic Assignment. Copyright © by SIAM.