Rainer E. Burkard, Eranda Çela, Günter Rote, and Gerhard J. Woeginger:

The quadratic assignment problem with a monotone Anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases

  1. Extended abstract in: "Integer Programming and Combinatorial Optimization". Proceedings of the 5th International IPCO Conference, Vancouver, Canada, June 1996. Editors: W. H. Cunningham, S. T. McCormick, and M. Queyranne. Lecture Notes in Computer Science 1084, Springer-Verlag, 1996, pp. 204–218. doi:10.1007/3-540-61310-2_16
  2. Mathematical Programming 82 (1998), 125–158. doi:10.1007/BF01585868


We investigate a restricted version of the Quadratic Assignment Problem (QAP), where one of the coefficient matrices is an Anti-Monge matrix with non-decreasing rows and columns and the other coefficient matrix is a symmetric Toeplitz matrix. This restricted version is called the Anti-Monge-Toeplitz QAP. There are three well-known combinatorial problems that can be modeled via the Anti-Monge-Toeplitz QAP: We identify conditions on the Toeplitz matrix that lead to a simple solution for the Anti-Monge–Toeplitz QAP: The optimal permutation can be given in advance without regarding the numerical values of the data. The resulting theorems generalize and unify several known results on problems (P1), (P2), and (P3). We also show that the Turbine Problem is NP-hard and consequently, that the Anti-Monge–Toeplitz QAP is NP-hard in general.

  PostScript file (gzipped)   pdf file   TeX .dvi file (gzipped)   free PDF view@Springer
other papers about this subject
Last update: August 15, 2017.