Well-solvable cases of the QAP with block-structured matrices

DOI10.1016/j.dam.2015.01.005zbMath1323.90057arXiv1402.3500OpenAlexW1967778369MaRDI QIDQ2345597

Eranda Çela, Vladimir G. Deǐneko, Gerhard J. Woeginger

Publication date: 22 May 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.3500

zbMATH Keywords

computational complexitycombinatorial optimizationbalanced cutproduct matrixcut problemMonge condition

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items

Complexity and Polynomially Solvable Special Cases of QUBO, Characterizing linearizable QAPs by the level-1 reformulation-linearization technique, An LP-based characterization of solvable QAP instances with chess-board and graded structures, Graph Similarity and Approximate Isomorphism, New special cases of the quadratic assignment problem with diagonally structured coefficient matrices, A New Tractable Case of the QAP with a Robinson Matrix, The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Wiener maximum quadratic assignment problem
• A solvable case of the quadratic assignment problem
• The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
• The quadratic assignment problem. Theory and algorithms
• Another well-solvable case of the QAP: maximizing the job completion time variance
• Monge matrices make maximization manageable
• Perspectives of Monge properties in optimization
• Assignment Problems and the Location of Economic Activities
• Assignment Problems
• The cone of Monge matrices: Extremal rays and applications
• The complexity of satisfiability problems