Re. Burkard et al., THE QUADRATIC ASSIGNMENT PROBLEM WITH A MONOTONE ANTI-MONGE AND A SYMMETRICAL TOEPLITZ MATRIX - EASY AND HARD CASES, Mathematical programming, 82(1-2), 1998, pp. 125-158
Citations number
23
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Computer Science Software Graphycs Programming","Operatione Research & Management Science",Mathematics,"Computer Science Software Graphycs Programming
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.