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

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
ReferenceBot (talk | contribs)
Changed an Item
 
(5 intermediate revisions by 4 users not shown)
Property / author
 
Property / author: Valery S. Gordon / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Rainer E. Burkard / rank
Normal rank
 
Property / author
 
Property / author: Valery S. Gordon / rank
 
Normal rank
Property / reviewed by
 
Property / reviewed by: Rainer E. Burkard / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/s10852-005-9013-2 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2002576440 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A unified approach to simple special cases of extremal permutation problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some problems in optimal allocation of large-volume memories / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3059506 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Quadratic assignment problems with additively monotone matrices and incomplete anti-Monge matrices: conditions for effective solvability / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3747197 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Assignment Problems and the Location of Economic Activities / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4062939 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4321546 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal product and server locations in one-dimensional storage racks / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

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
    0 references
    0 references
    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

    Identifiers