The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure
From MaRDI portal
Publication:1785334
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
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
