The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure

DOI10.1016/J.ORL.2014.12.009zbMath1408.90164arXiv1407.2801OpenAlexW2169867839MaRDI QIDQ1785334

Matteo Seminaroti, Monique Laurent

Publication date: 28 September 2018

Published in: Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

seriationquadratic assignment problemRobinson (dis)similaritywell solvable special case

Mathematics Subject Classification ID

Quadratic programming (90C20) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Toeplitz, Cauchy, and related matrices (15B05)

Related Items (11)

Reconstruction of line-embeddings of graphons ⋮ Convex Relaxations for Permutation Problems ⋮ Robinsonian matrices: recognition challenges ⋮ Characterizing linearizable QAPs by the level-1 reformulation-linearization technique ⋮ An LP-based characterization of solvable QAP instances with chess-board and graded structures ⋮ The complexity of comparing multiply-labelled trees by extending phylogenetic-tree metrics ⋮ Continuation methods for approximate large scale object sequencing ⋮ An experimental comparison of seriation methods for one-mode two-way data ⋮ New special cases of the quadratic assignment problem with diagonally structured coefficient matrices ⋮ A New Tractable Case of the QAP with a Robinson Matrix ⋮ A Lex-BFS-based recognition algorithm for Robinsonian matrices

Cites Work

• An optimal algorithm to recognize Robinsonian dissimilarities
• Well solvable cases of the quadratic assignment problem with monotone and bimonotone matrices
• A solvable case of the quadratic assignment problem
• On the consecutive ones property
• The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
• Recognition of Robinsonian dissimilarities
• Well-solvable cases of the QAP with block-structured matrices
• Incidence matrices and interval graphs
• Incidence matrices, interval graphs and seriation in archeology
• 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
• A unified approach to simple special cases of extremal permutation problems
• An Analysis of Spectral Envelope Reduction via Quadratic Assignment Problems
• The structure of circular decomposable metrics
• Edgeconvex Circuits and the Traveling Salesman Problem
• A spectral algorithm for envelope reduction of sparse matrices
• Seriation and matrix reordering methods: An historical overview

This page was built for publication: The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure