Rainer E. Burkard, Eranda Çela, Günter Rote, and Gerhard J.
Woeginger:
The quadratic assignment problem with a monotone AntiMonge and a symmetric
Toeplitz matrix: Easy and hard cases
 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, SpringerVerlag, 1996, pp. 204–218.
doi:10.1007/3540613102_16

Mathematical Programming 82 (1998), 125–158. doi:10.1007/BF01585868
Abstract
We investigate a restricted version of the Quadratic Assignment Problem
(QAP), where one of the coefficient matrices is an AntiMonge matrix with
nondecreasing rows and columns and the other coefficient matrix is a symmetric
Toeplitz matrix. This restricted version is called the AntiMongeToeplitz
QAP. There are three wellknown combinatorial problems that can be modeled
via the AntiMongeToeplitz 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 center
of gravity of the resulting system to the center of the polygon is minimized.

(P2) The Traveling Salesman Problem on symmetric Monge distance matrices.

(P3) The arrangement of data records with given access probabilities in
a linear storage medium in order to minimize the average access time.
We identify conditions on the Toeplitz matrix that lead to a simple solution
for the AntiMonge–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 NPhard and consequently,
that the AntiMonge–Toeplitz QAP is NPhard in general.
Last update: August 15, 2017.