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

DOI10.1016/J.DISOPT.2011.03.002MaRDI QIDQ665995zbMATHOpenAlexFDO

Authors Güneş Erdogăn, B. 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 complexitylinear assignment problemquadratic assignment problempolynomial time solvability

Mathematics Subject Classification ID

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

Recommendations

• Linear programming insights into solvable cases of the quadratic assignment problem
• New linearizations of quadratic assignment problems
• A solvable case of the quadratic assignment problem
• A new solution method by linearization for a special kind of quadratic assignment problem
• A new linearization method for quadratic assignment problems
• scientific article; zbMATH DE number 3982880
• A polynomially solvable class of quadratic semi-assignment problems
• Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers
• scientific article; zbMATH DE number 1568992

Cites work

• scientific article; zbMATH DE number 176471 (Why is no real title available?)
• A solvable case of the quadratic assignment problem
• Assignment Problems
• Assignment Problems and the Location of Economic Activities
• P-Complete Approximation Problems
• QAPLIB - a quadratic assignment problem library
• Special cases of the quadratic assignment problem
• The quadratic assignment problem
• The quadratic assignment problem. Theory and algorithms

Cited in

(17)

• The linearization problem of a binary quadratic problem and its applications
• An LP-based characterization of solvable QAP instances with chess-board and graded structures
• Linearizable special cases of the quadratic shortest path problem
• Generating QAP instances with known optimum solution and additively decomposable cost function
• An \(O(n^{4})\) algorithm for the QAP linearization problem
• Linear programming insights into solvable cases of the quadratic assignment problem
• Room allocation: a polynomial subcase of the quadratic assignment problem
• Subclasses of solvable problems from classes of combinatorial optimization problems
• Well solvable cases of the quadratic assignment problem with monotone and bimonotone matrices
• Quadratic assignment problems on series-parallel digraphs
• A linear time algorithm for linearizing quadratic and higher-order shortest path problems
• scientific article; zbMATH DE number 591196 (Why is no real title available?)
• Linearizable special cases of the QAP
• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• Characterizing linearizable QAPs by the level-1 reformulation-linearization technique
• Classes of quadratic assignment problem instances: Isomorphism and difficulty measure using a statistical approach
• Best reduction of the quadratic semi-assignment problem

Describes a project that uses

Uses Software

• QAPLIB

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

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