A solvable case of the quadratic assignment problem

DOI10.1016/S0167-6377(97)00047-3zbMath0910.90226OpenAlexW2170954130MaRDI QIDQ1267182

Gerhard J. Woeginger, Vladimir G. Deǐneko

Publication date: 3 December 1998

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(97)00047-3

zbMATH Keywords

quadratic assignmentcirculant matrixtravelling salesmanKalmanson matrix

Mathematics Subject Classification ID

Quadratic programming (90C20) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items

Linearizable special cases of the QAP ⋮ A survey for the quadratic assignment problem ⋮ A note on a polynomial time solvable case of the quadratic assignment problem ⋮ A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems ⋮ The three-dimensional matching problem in kalmanson matrices ⋮ Characterizing linearizable QAPs by the level-1 reformulation-linearization technique ⋮ An LP-based characterization of solvable QAP instances with chess-board and graded structures ⋮ The multi-stripe travelling salesman problem ⋮ The Wiener maximum quadratic assignment problem ⋮ Two classes of quadratic assignment problems that are solvable as linear assignment problems ⋮ Polynomially solvable cases of the bipartite traveling salesman problem ⋮ New special cases of the quadratic assignment problem with diagonally structured coefficient matrices ⋮ Another well-solvable case of the QAP: maximizing the job completion time variance ⋮ Selected topics on assignment problems ⋮ A New Tractable Case of the QAP with a Robinson Matrix ⋮ The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure ⋮ Linear programming insights into solvable cases of the quadratic assignment problem ⋮ Four-point conditions for the TSP: the complete complexity classification ⋮ Well-solvable cases of the QAP with block-structured matrices

Uses Software

• ZRAM

Cites Work

• A canonical decomposition theory for metrics on a finite set
• Generating quadratic assignment test problems with known optimal permutations
• The Quadratic Assignment Problem
• Assignment Problems and the Location of Economic Activities
• The quadratic assignment problem with a monotone anti-monge and a symmetric toeplitz matrix: Easy and hard cases
• Edgeconvex Circuits and the Traveling Salesman Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item