A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems

DOI10.1016/j.disopt.2013.02.003zbMath1506.90232OpenAlexW1980190773MaRDI QIDQ1662098

Santosh N. Kabadi, Abraham P. Punnen

Publication date: 17 August 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2013.02.003

zbMATH Keywords

linearizationquadratic assignment problempolynomial algorithms

Mathematics Subject Classification ID

Quadratic programming (90C20) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items

Linearizable special cases of the QAP, The Rank-One Quadratic Assignment Problem, The quadratic cycle cover problem: special cases and efficient bounds, On a linearization technique for solving the quadratic set covering problem and variations, 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, An LP-based characterization of solvable QAP instances with chess-board and graded structures, 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, Linear programming insights into solvable cases of the quadratic assignment problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using well-solvable quadratic assignment problems for VLSI interconnect applications
• On the maximal Wiener index and related questions
• The Wiener maximum quadratic assignment problem
• Two classes of quadratic assignment problems that are solvable as linear assignment problems
• A survey for the quadratic assignment problem
• Well solvable cases of the quadratic assignment problem with monotone and bimonotone matrices
• A note on a polynomial time solvable case of the quadratic assignment problem
• Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems
• Special cases of the quadratic assignment 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
• Another well-solvable case of the QAP: maximizing the job completion time variance
• Room allocation: a polynomial subcase of the quadratic assignment problem
• Dynamic programming for the quadratic assignment problem on trees
• Efficiently solvable cases of quadratic assignment problem with generalized monotonic and incomplete anti-Monge matrices
• The Quadratic Assignment Problem
• An O(n⁴) Algorithm for the QAP Linearization Problem
• Polynomial algorithms for solving the quadratic assignment problem on networks
• Assignment Problems and the Location of Economic Activities
• A contribution to quadratic assignment problems
• P-Complete Approximation Problems
• The Distribution of Values in the Quadratic Assignment Problem