Linearizable special cases of the QAP

DOI10.1007/S10878-014-9821-2MaRDI QIDQ266060zbMATHOpenAlexFDO

Authors Eranda Çela, Gerhard J. Woeginger, Vladimir G. Deineko

Publication date 13 April 2016

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.6510

zbMATH Keywords

computational complexitycombinatorial optimizationlinear assignment problemquadratic assignment problem

Mathematics Subject Classification ID

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

Abstract: We consider special cases of the quadratic assignment problem (QAP) that are linearizable in the sense of Bookhold. We provide combinatorial characterizations of the linearizable instances of the weighted feedback arc set QAP, and of the linearizable instances of the traveling salesman QAP. As a by-product, this yields a new well-solvable special case of the weighted feedback arc set problem.

Recommendations

• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• An \(O(n^{4})\) algorithm for the QAP linearization problem
• Two classes of quadratic assignment problems that are solvable as linear assignment problems
• A contribution to quadratic assignment problems
• The quadratic assignment problem. Theory and algorithms

Cites work

• scientific article; zbMATH DE number 4027206 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• A branch-and-cut algorithm for quadratic assignment problems based on linearizations
• A characterization of linear admissible transformations for the m- travelling salesmen problem
• A contribution to quadratic assignment problems
• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• A solvable case of the quadratic assignment problem
• An \(O(n^{4})\) algorithm for the QAP linearization problem
• Another well-solvable case of the QAP: maximizing the job completion time variance
• Assignment Problems
• Assignment Problems and the Location of Economic Activities
• The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
• The quadratic assignment problem. Theory and algorithms
• Two classes of quadratic assignment problems that are solvable as linear assignment problems
• Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey

Cited in

(13)

• Revisiting some classical linearizations of the quadratic binary optimization problem and linkages with constraint aggregations
• 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
• The constant objective value property for multidimensional assignment problems
• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• Combinatorial optimization with interaction costs: complexity and solvable cases
• An \(O(n^{4})\) algorithm for the QAP linearization problem
• 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
• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• Characterizing linearizable QAPs by the level-1 reformulation-linearization technique

This page was built for publication: Linearizable special cases of the QAP

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