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

DOI10.1016/j.dam.2015.01.005zbMath1323.90057arXiv1402.3500MaRDI 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 complexity; combinatorial optimization; balanced cut; product matrix; cut problem; Monge condition

Mathematics Subject Classification ID

90C27: Combinatorial optimization

90B80: Discrete location and assignment

Related Items

Complexity and Polynomially Solvable Special Cases of QUBO, Graph Similarity and Approximate Isomorphism, A New Tractable Case of the QAP with a Robinson Matrix, An LP-based characterization of solvable QAP instances with chess-board and graded structures, New special cases of the quadratic assignment problem with diagonally structured coefficient matrices, 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