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 (19)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: A solvable case of the quadratic assignment problem