New special cases of the quadratic assignment problem with diagonally structured coefficient matrices

DOI10.1016/j.ejor.2017.12.024zbMath1403.90471arXiv1609.06223MaRDI QIDQ1754256

Eranda Çela, Vladimir G. Deǐneko, Gerhard J. Woeginger

Publication date: 30 May 2018

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1609.06223

zbMATH Keywords

combinatorial optimization; quadratic assignment; Monge matrix; Kalmanson matrix; Robinsonian

Mathematics Subject Classification ID

90C27: Combinatorial optimization

90B80: Discrete location and assignment

Related Items

Quadratic assignment problem variants: a survey and an effective parallel memetic iterated tabu search, The linearization problem of a binary quadratic problem and its applications, Estimation of Monge matrices

Cites Work

• Unnamed Item
• Unnamed Item
• The three-dimensional matching problem in kalmanson matrices
• The Wiener maximum quadratic assignment problem
• Extreme Hamiltonian lines
• A survey for the quadratic assignment problem
• Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems
• A canonical decomposition theory for metrics on a finite set
• 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 Steiner tree problem in Kalmanson matrices and in circulant matrices
• The quadratic assignment problem. Theory and algorithms
• Another well-solvable case of the QAP: maximizing the job completion time variance
• Combinatorial optimization and hierarchical classifications
• The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure
• A note on the metric properties of trees
• Perspectives of Monge properties in optimization
• Well-solvable cases of the QAP with block-structured matrices
• Sub-dominant theory in numerical taxonomy
• Mathematical classification and clustering
• Combinatorial Data Analysis
• Assignment Problems and the Location of Economic Activities
• Convex Relaxations for Permutation Problems
• Assignment Problems
• P-Complete Approximation Problems
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• Three easy special cases of the euclidean travelling salesman problem
• Sometimes Travelling is Easy: The Master Tour Problem
• Edgeconvex Circuits and the Traveling Salesman Problem
• The cone of Monge matrices: Extremal rays and applications
• Seriation and matrix reordering methods: An historical overview
• Balancing profits and costs on trees
• Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition
• Extrema in Space-Time
• A New Tractable Case of the QAP with a Robinson Matrix