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

2014/07/10 by Monique Laurent, Laurent, Monique, Matteo Seminaroti +1 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #Optimization and Control (math.OC) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1407.2801

openalex publication_date 2014/07/10 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28

Abstract

We present a new polynomially solvable case of the Quadratic Assignment\nProblem in Koopmans-Beckman form QAP(A,B), by showing that the identity\npermutation is optimal when A and B are respectively a Robinson similarity\nand dissimilarity matrix and one of A or B is a Toeplitz matrix. A Robinson\n(dis)similarity matrix is a symmetric matrix whose entries (increase) decrease\nmonotonically along rows and columns when moving away from the diagonal, and\nsuch matrices arise in the classical seriation problem.\n

Citations

• Assignment Problems and the Location of Economic Activities

Cited by

• Diamond transports in quadratic-form and distorted optimal transport

Related

• New special cases of the Quadratic Assignment Problem with diagonally\n structured coefficient matrices
• Well-solvable cases of the QAP with block-structured matrices
• The quadratic assignment problem: the linearization of Xia and Yuan is weaker than the linearization of Adams and Johnson and a family of cuts to narrow the gap
• Exactness Conditions for Semidefinite Relaxations of the Quadratic Assignment Problem
• On the Complexity of Some Facet-Defining Inequalities of the\n QAP-polytope