Well solvable cases of the quadratic assignment problem with monotone and bimonotone matrices (Q853797): Difference between revisions
From MaRDI portal
Latest revision as of 22:17, 24 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Well solvable cases of the quadratic assignment problem with monotone and bimonotone matrices |
scientific article |
Statements
Well solvable cases of the quadratic assignment problem with monotone and bimonotone matrices (English)
0 references
17 November 2006
0 references
A general theorem of \textit{R. E. Burkard, E. Çela, G. Rote} and \textit{G. J. Woeginger} [Math. Program. 82, 125--158 (1998; Zbl 0949.90077)] asserts that a quadratic assignment problem QAP\((A,B)\) where \(A\) is a benevolent Toeplitz matrix and \(B\) is a monotone Anti Monge matrix is solved by the cyclic permutation \(\varphi =(1,3,5,\dots,n,\dots,6,4,2)\). In this paper two sets of conditions for the matrices \(A\) and \(B\) are derived which guarantee that the cyclic permutation \(\varphi =(1,3,5,\dots,n,\dots,6,4,2)\) is optimal for QAP\((A,B)\). The new conditions rely on order relations for the entries of matrices \(A\) and \(B\) and do not impose in general that \(A\) is a Toeplitz matrix and \(B\) is an Anti Monge matrix.
0 references
quadratic assignment problem
0 references
special case
0 references
0 references