Linearizable special cases of the QAP

DOI10.1007/s10878-014-9821-2zbMath1344.90053arXiv1409.6510OpenAlexW1985792422MaRDI QIDQ266060

Eranda Çela, Gerhard J. Woeginger, Vladimir G. Deǐneko

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 optimizationquadratic assignment problemlinear assignment problem

Mathematics Subject Classification ID

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

Related Items

Linearizable 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 ⋮ Characterizing linearizable QAPs by the level-1 reformulation-linearization technique ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two classes of quadratic assignment problems that are solvable as linear assignment problems
• 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 solvable case of the quadratic assignment problem
• 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
• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• Another well-solvable case of the QAP: maximizing the job completion time variance
• An O(n⁴) Algorithm for the QAP Linearization Problem
• Assignment Problems and the Location of Economic Activities
• A contribution to quadratic assignment problems
• Assignment Problems
• Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey