Linearizable special cases of the QAP

DOI10.1007/S10878-014-9821-2MaRDI QIDQ266060zbMATH OpenOpenAlexFDO

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

combinatorial optimizationcomputational complexitylinear assignment problemquadratic assignment problem

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• 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

(16)

• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• The bilinear assignment problem: complexity and polynomially solvable special cases
• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• Special cases of the quadratic shortest path 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
• Linearizable special cases of the quadratic shortest path problem
• An \(O(n^{4})\) algorithm for the QAP linearization 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: 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)