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

DOI10.1007/BF01585868MaRDI QIDQ1290637zbMATHFDO

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)

zbMATH Keywords

Toeplitz matricesquadratic assignmentpolynomially solvablespecial casesAnti-Monge 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

• 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?)
• Assignment Problems and the Location of Economic Activities
• Balanced Loading
• Balancing hydraulic turbine runners - A discrete combinatorial optimization problem
• Extreme Hamiltonian lines
• 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

(38)

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

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)