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

DOI10.1016/J.DISOPT.2013.02.003zbMATH Open1506.90232OpenAlexW1980190773MaRDI QIDQ1662098FDOQ1662098

Authors: Abraham P. Punnen, Santosh N. Kabadi 

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

Recommendations

• An \(O(n^{4})\) algorithm for the QAP linearization problem
• Linearizable special cases of the QAP
• A new linearization method for quadratic assignment problems
• scientific article; zbMATH DE number 1302195
• A branch-and-cut algorithm for quadratic assignment problems based on linearizations

zbMATH Keywords

quadratic assignment problemlinearizationpolynomial algorithms

Mathematics Subject Classification ID

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

Cites Work

• Network flows. Theory, algorithms, and applications.
• The Distribution of Values in 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
• An \(O(n^{4})\) algorithm for the QAP linearization problem
• Assignment Problems and the Location of Economic Activities
• A contribution to quadratic assignment problems
• Two classes of quadratic assignment problems that are solvable as linear assignment problems
• P-Complete Approximation Problems
• A survey for the quadratic assignment problem
• The Wiener maximum quadratic assignment problem
• Title not available (Why is that?)
• Dynamic programming for the quadratic assignment problem on trees
• The quadratic assignment problem
• Using well-solvable quadratic assignment problems for VLSI interconnect applications
• Well solvable cases of the quadratic assignment problem with monotone and bimonotone matrices
• On the maximal Wiener index and related questions
• Special cases of the quadratic assignment problem
• Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems
• Title not available (Why is that?)
• Room allocation: a polynomial subcase of the quadratic assignment problem
• Efficiently solvable cases of quadratic assignment problem with generalized monotonic and incomplete anti-Monge matrices
• Generalization of conditions for the strong solvability of a quadratic assignment problem with anti-Monge and Toeplitz matrices
• A note on a polynomial time solvable case of the quadratic assignment problem
• Polynomial algorithms for solving the quadratic assignment problem on networks

Cited In (18)

• The Rank-One Quadratic Assignment Problem
• Linearizable special cases of the QAP
• The linearization problem of a binary quadratic problem and its applications
• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• An LP-based characterization of solvable QAP instances with chess-board and graded structures
• Linear programming insights into solvable cases of the quadratic assignment problem
• Linearizable special cases of the quadratic shortest path problem
• A new linearization method for quadratic assignment problems
• On a linearization technique for solving the quadratic set covering problem and variations
• An \(O(n^{4})\) algorithm for the QAP linearization problem
• The bilinear assignment problem: complexity and polynomially solvable special cases
• The constant objective value property for multidimensional assignment problems
• Combinatorial optimization with interaction costs: complexity and solvable cases
• The quadratic cycle cover problem: special cases and efficient bounds
• Revisiting some classical linearizations of the quadratic binary optimization problem and linkages with constraint aggregations
• Characterizing linearizable QAPs by the level-1 reformulation-linearization technique
• Special cases of the quadratic shortest path problem
• A linear time algorithm for linearizing quadratic and higher-order shortest path problems

This page was built for publication: A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems

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