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

Citation
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
Journal title
ISSN journal
00255610
Volume
82
Issue
1-2
Year of publication
1998
Pages
125 - 158
Database
ISI
SICI code
0025-5610(1998)82:1-2<125:TQAPWA>2.0.ZU;2-4
Abstract
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.