On the Maximum Quadratic Assignment Problem

• 成果类型: Article
• 署名作者: Nagarajan, Viswanath; Sviridenko, Maxim
• 署名单位: International Business Machines (IBM); IBM USA
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1090.0418
• 发表日期: 2009
• 页码: 859-868
• 关键词: dense k-subgraph; Approximation algorithms

摘要

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 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) := Sigma(i,j is an element of[n], i not equal j) w(i,j) . d(pi(i), pi(j)). In this paper, we study the maximum quadratic assignment problem, where the goal is to find a permutation pi that maximizes Q(pi). We give an (O) over tilde (root 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 approximate to n(1/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) approximate to 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 (Omega) over tilde (root n) for general maximum quadratic assignment.