An O(n^4) algorithm for the QAP linearization problem

DOI10.1287/MOOR.1110.0509MaRDI QIDQ2884300zbMATH OpenOpenAlexFDO

Authors 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

linearizationpolynomial algorithmsquadratic assignment problemsolvable cases

Mathematics Subject Classification ID

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

Recommendations

• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• Linearizable special cases of the QAP
• scientific article; zbMATH DE number 1302195
• Two classes of quadratic assignment problems that are solvable as linear assignment problems
• A contribution to quadratic assignment problems

Cited in

(19)

• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• On a linearization technique for solving the quadratic set covering problem and variations
• The bilinear assignment problem: complexity and polynomially solvable special cases
• 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
• The quadratic cycle cover problem: special cases and efficient bounds
• 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
• Linearizable special cases of the QAP
• Linearizable special cases of the quadratic shortest path problem
• 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
• Revisiting some classical linearizations of the quadratic binary optimization problem and linkages with constraint aggregations
• A polyhedral characterization of linearizable quadratic combinatorial optimization problems
• The independent quadratic assignment problem: complexity and polynomially solvable special cases
• A linear time algorithm for linearizing quadratic and higher-order shortest path problems

This page was built for publication: An \(O(n^{4})\) algorithm for the QAP linearization problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2884300)