An O(n4) Algorithm for the QAP Linearization Problem

DOI10.1287/moor.1110.0509zbMath1243.90187OpenAlexW1964265873MaRDI QIDQ2884300

Abraham P. Punnen, Santosh N. Kabadi

Publication date: 24 May 2012

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.1110.0509

zbMATH Keywords

linearizationquadratic assignment problempolynomial algorithmssolvable cases

Mathematics Subject Classification ID

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

Related Items (15)

Linearizable special cases of the QAP ⋮ A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems ⋮ The quadratic cycle cover problem: special cases and efficient bounds ⋮ On a linearization technique for solving the quadratic set covering problem and variations ⋮ Linearizable special cases of the quadratic shortest path problem ⋮ The bilinear assignment problem: complexity and polynomially solvable special cases ⋮ A linear time algorithm for linearizing quadratic and higher-order shortest path problems ⋮ Characterizing linearizable QAPs by the level-1 reformulation-linearization technique ⋮ An LP-based characterization of solvable QAP instances with chess-board and graded structures ⋮ A characterization of linearizable instances of the quadratic minimum spanning tree problem ⋮ The constant objective value property for multidimensional assignment problems ⋮ Combinatorial optimization with interaction costs: complexity and solvable cases ⋮ The linearization problem of a binary quadratic problem and its applications ⋮ Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems ⋮ Linear programming insights into solvable cases of the quadratic assignment problem

This page was built for publication: An O(n⁴) Algorithm for the QAP Linearization Problem