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 = (w_{i, j}) and D = (d_{i, j}). Given matrices W, D, and a permutation π: [n] → [n], the objective function is [EQUATION]. 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 [EQUATION] approximation algorithm. This improves over the previously bestknown 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 [EQUATION] for general Maximum Quadratic Assignment.

REFERENCES

• 1: W. P. Adams and T. A. Johnson, Improved Linear Programming-based Lower Bounds for the Quadratic Assignment Problem, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 16, 1994, 43--77.
• 2: A. Ageev and M. Sviridenko, Pipage rounding: a new method of constructing algorithms with proven performance guarantee, J. Comb. Optim. 8 (2004), pp. 307--328.
• 3: Esther M. Arkin , Refael Hassin , Shlomi Rubinstein , Maxim Sviridenko, Approximations for Maximum Transportation with Permutable Supply Vector and Other Capacitated Star Packing Problems, Algorithmica, v.39 n.2, p.175-187, February 2004 [doi>10.1007/s00453-004-1087-0]
• 4: Esther M. Arkin , Refael Hassin , Maxim Sviridenko, Approximating the maximum quadratic assignment problem, Information Processing Letters, v.77 n.1, p.13-16, January 31, 2001 [doi>10.1016/S0020-0190(00)00151-4]
• 5: S. Arora, A. Frieze and H. Kaplan, A new rounding procedure for the assignment problem with applications to dense graph arrangement problems, Mathematical Programming, 92(1), 2002, 1--36.
• 6: R. E. Burkard, E. Cela, P. Pardalos and L. S. Pitsoulis, The quadratic assignment problem, In Handbook of Combinatorial Optimization, D. Z. Du, P. M. Pardalos (Eds.), Vol. 3, Kluwer Academic Publishers, 1998, 241--339.
• 7: Eranda Cela, The Quadratic Assignment Problem: Theory and Algorithms, Springer, 1998.
• 8: Uriel Feige, Guy Kortsarz, and David Peleg, The Dense k-Subgraph Problem, Algorithmica, 29(3), 410--421, 2001.
• 9: Uriel Feige , Michael Langberg, Approximation algorithms for maximization problems arising in graph partitioning, Journal of Algorithms, v.41 n.2, p.174-211, November 2001 [doi>10.1006/jagm.2001.1183]
• 10: T. Feo and M. Khellaf, A class of bounded approximation algorithms for graph partitioning, Networks, 20, 1990, 181--195.
• 11: Nili Guttmann-Beck , Refael Hassin, Approximation algorithms for minimum tree partition, Discrete Applied Mathematics, v.87 n.1-3, p.117-137, Oct., 5, 1998 [doi>10.1016/S0166-218X(98)00052-3]
• 12: Nili Guttmann-Beck , Refael Hassin, Approximation algorithms for min-sum p-clustering, Discrete Applied Mathematics, v.89 n.1-3, p.125-142, Dec. 1998 [doi>10.1016/S0166-218X(98)00100-0]
• 13: R. Hassin, A. Levin and M. Sviridenko, Approximating the minimum quadratic assignment problems, Submitted for publication.
• 14: Refael Hassin , Shlomi Rubinstein, Robust Matchings, SIAM Journal on Discrete Mathematics, v.15 n.4, p.530-537, 2002 [doi>10.1137/S0895480198332156]
• 15: E. M. Loilola, N. M. M. De Abreu, P. O. BoaventuraNetto, P. M. Hahn, and T. Querido, A survey for the quadratic assignment problem, Invited Review, European Journal of Operational Research, 176, 657--690, 2006.
• 16: P. Pardalos and H. Wolkowitz, eds., Proceedings of the DIMACS Workshop on Quadratic Assignment Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 16, 1994.
• 17: Erez Petrank, The hardness of approximation: gap location, Computational Complexity, v.4 n.2, p.133-157, April 1994 [doi>10.1007/BF01202286]
• 18: M. Queyranne, Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems, Operations Research Letters, 4, 1986, 231--234.
• 19: Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976 [doi>10.1145/321958.321975]
• 20: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 21: N. C. Wormald, Models of random regular graphs. Surveys in Combinatorics, 1999, J. D. Lamb and D. A. Preece, eds. London Mathematical Society Lecture Note Series, vol 276, pp. 239--298.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms