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

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

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