Two classes of quadratic assignment problems that are solvable as linear assignment problems

DOI10.1016/j.disopt.2011.03.002zbMath1233.90239OpenAlexW1964357023MaRDI QIDQ665995

Güneş Erdoğan, Barbaros C. Tansel

Publication date: 7 March 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/11693/21836

zbMATH Keywords

computational complexityquadratic assignment problemlinear assignment problempolynomial time solvability

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Linear-quadratic optimal control problems (49N10) Discrete location and assignment (90B80)

Related Items (9)

Linearizable special cases of the QAP ⋮ A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems ⋮ Linearizable special cases of the quadratic shortest path problem ⋮ Generating QAP instances with known optimum solution and additively decomposable cost function ⋮ 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 ⋮ The linearization problem of a binary quadratic problem and its applications ⋮ Linear programming insights into solvable cases of the quadratic assignment problem

Uses Software

• QAPLIB

Cites Work

• Special cases of the quadratic assignment problem
• A solvable case of the quadratic assignment problem
• QAPLIB - a quadratic assignment problem library
• The quadratic assignment problem. Theory and algorithms
• The Quadratic Assignment Problem
• Assignment Problems and the Location of Economic Activities
• Assignment Problems
• P-Complete Approximation Problems
• Unnamed Item

This page was built for publication: Two classes of quadratic assignment problems that are solvable as linear assignment problems