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

DOI10.1007/BF01585868zbMATH Open0949.90077MaRDI QIDQ1290637FDOQ1290637

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)

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

zbMATH Keywords

Toeplitz matricesquadratic assignmentpolynomially solvablespecial casesAnti-Monge matrices

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
• Assignment Problems and the Location of Economic Activities
• Title not available (Why is that?)
• Perspectives of Monge properties in optimization
• Extreme Hamiltonian lines
• Balanced Loading
• The quadratic assignment problem
• Title not available (Why is that?)
• Solving large quadratic assignment problems in parallel
• Balancing hydraulic turbine runners - A discrete combinatorial optimization problem
• Some problems in optimal allocation of large-volume memories
• Title not available (Why is that?)

Cited In (38)

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

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)