The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases

DOI10.1007/BF01585868MaRDI QIDQ1290637zbMATH OpenFDO

Authors Rainer E. Burkard, Eranda Çela, Günter Rote, Gerhard J. Woeginger

Publication date 28 June 1999

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01585868

zbMATH Keywords

Anti-Monge matricespolynomially solvablequadratic assignmentspecial casesToeplitz matrices

Mathematics Subject Classification ID

Quadratic programming (90C20) Combinatorial optimization (90C27)

Recommendations

• The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: easy and hard cases
• Well solvable cases of the quadratic assignment problem with monotone and bimonotone matrices
• Quadratic assignment problems with additively monotone matrices and incomplete anti-Monge matrices: conditions for effective solvability
• The quadratic assignment problem. Theory and algorithms

Cites work

• Assignment Problems and the Location of Economic Activities
• Balanced Loading
• Balancing hydraulic turbine runners - A discrete combinatorial optimization problem
• Extreme Hamiltonian lines
• scientific article; zbMATH DE number 3898613 (Why is no real title available?)
• scientific article; zbMATH DE number 3480380 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 714526 (Why is no real title available?)
• Perspectives of Monge properties in optimization
• Solving large quadratic assignment problems in parallel
• Some problems in optimal allocation of large-volume memories
• The quadratic assignment problem
• The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases

Cited in

(43)

• Symmetrization of nonsymmetric quadratic assignment problems and the Hoffman-Wielandt inequality
• The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
• Efficiently solvable special cases of hard combinatorial optimization problems
• The doubly graded matrix cone and Ferrers matrices
• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• The bilinear assignment problem: complexity and polynomially solvable special cases
• The multi-stripe travelling salesman problem
• New special cases of the quadratic assignment problem with diagonally structured coefficient matrices
• Another well-solvable case of the QAP: maximizing the job completion time variance
• The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure
• Perspectives of Monge properties in optimization
• String shuffle: circuits and graphs
• Dynamic programming for the quadratic assignment problem on trees
• A new algorithm for solving a special matching problem with a general form value function under constraints
• Linear programming insights into solvable cases of the quadratic assignment problem
• Well-solvable cases of the QAP with block-structured matrices
• Robinsonian matrices: recognition challenges
• A parallel water flow algorithm with local search for solving the quadratic assignment problem
• Efficiently solvable cases of quadratic assignment problem with generalized monotonic and incomplete anti-Monge matrices
• Unshuffling a square is NP-hard
• Linearizable special cases of the QAP
• Bilinear Assignment Problem: Large Neighborhoods and Experimental Analysis of Algorithms
• Using well-solvable quadratic assignment problems for VLSI interconnect applications
• A unified approach to simple special cases of extremal permutation problems
• The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: easy and hard cases
• Graph similarity and approximate isomorphism
• Complexity and polynomially solvable special cases of QUBO
• Quadratic assignment problems with additively monotone matrices and incomplete anti-Monge matrices: conditions for effective solvability
• A new tractable case of the QAP with a Robinson matrix
• Characterizing linearizable QAPs by the level-1 reformulation-linearization technique
• One-Dimensional Carousel Storage Problems: Applications, Review and Generalizations
• An LP-based characterization of solvable QAP instances with chess-board and graded structures
• The Wiener maximum quadratic assignment problem
• Conditions for the effective solvability of the quadratic choice problem. II
• A polyhedral characterization of linearizable quadratic combinatorial optimization problems
• Selected topics on assignment problems
• The independent quadratic assignment problem: complexity and polynomially solvable special cases
• Experimental analysis of algorithms for the independent quadratic assignment problem
• Conditions for the effective solvability of the quadratic choice problem. I
• Optimal wire ordering and spacing in low power semiconductor design
• 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

This page was built for publication: The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases

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