THE QUADRATIC ASSIGNMENT PROBLEM WITH A MONOTONE ANTI-MONGE AND A SYMMETRICAL TOEPLITZ MATRIX - EASY AND HARD CASES

This paper investigates a restricted version of the Quadratic Assignme nt Problem (QAP), where one of the coefficient matrices is an Anti-Mon ge matrix with non-decreasing rows and columns and the other coefficie nt matrix is a symmetric Toeplitz matrix. This restricted version is c alled the Anti-Monge-Toeplitz QAP. There are three well-known combinat orial problems that can be modeled via the Anti-Monge-Toeplitz QAP: (P 1) 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 minim ized. (P2) The Traveling Salesman Problem on symmetric Monge distance matrices. (P3) The arrangement of data records with given access proba bilities in a linear storage medium in order to minimize the average a ccess time. We identify conditions on the Toeplitz matrix B that lead to a simple solution for the Anti-Monge-Toeplitz QAP: The optimal perm utation can be given in advance without regarding the numerical values of the data, The resulting theorems generalize and unify several know n results on problems (P1), (P2), and(P3). We also show that the Turbi ne Problem is NP-hard and consequently, that the Anti-Monge-Toeplitz Q AP is NP-hard in general. (C) 1998 The Mathematical Programming Societ y, Inc. Published by Elsevier Science B.V.