Well solvable cases of the quadratic assignment problem with monotone and bimonotone matrices (Q853797): Difference between revisions

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.