The quadratic assignment problem with a monotone anti-monge and a symmetric toeplitz matrix: Easy and hard cases

The Anti-Monge-Toeplitz QAP (AMT-QAP) is a restricted version of the Quadratic Assignment Problem (QAP), with a monotone Anti-Monge matrix and a symmetric Toeplitz matrix. The following problems can be modeled via the AMT-QAP: (P1) The Turbine Problem, i. e. the assignment of given masses to the vertices of a regular polygon such that the distance of the gravity center of the resulting system to the polygon's center is minimized. (P2) The Traveling Salesman Problem on symmetric Monge matrices. (P3) The linear arrangement of records with given access probabilities in order to minimize the average access time. We identify conditions on the Toeplitz matrix that lead to polynomially solvable cases of the AMT-QAP. In each of these cases an optimal permutation can be given without regarding the numerical problem data. We show that the Turbine Problem is NP-hard and consequently, that the AMT-QAP is NP-hard