Linearizable special cases of the QAP

2014/09/23 by Eranda Çela, Eranda Cela, Cela, Eranda +5 · 1 citation
Computer Science · Engineering · Mathematics · #90C27 #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.1.6 #G.2.1 #G.2.2 #Optimization and Control (math.OC) #Optimization and Packing Problems #Optimization and Search Problems #Vehicle Routing Optimization Methods #acm:90C27 #cs.DS #math.OC #msc:90C27

paper · pdf · doi:10.48550/arxiv.1409.6510

11 pages

arxiv created 2014/09/23 · openalex publication_date 2014/09/23 · arxiv updated 2014/09/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

We consider special cases of the quadratic assignment problem (QAP) that are linearizable in the sense of Bookhold. We provide combinatorial characterizations of the linearizable instances of the weighted feedback arc set QAP, and of the linearizable instances of the traveling salesman QAP. As a by-product, this yields a new well-solvable special case of the weighted feedback arc set problem.

Cited by

• Diamond transports in quadratic-form and distorted optimal transport

Related

• 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
• On the Complexity of Some Facet-Defining Inequalities of the\n QAP-polytope
• Exactness Conditions for Semidefinite Relaxations of the Quadratic Assignment Problem
• A characterization of Linearizable instances of the Quadratic Traveling Salesman Problem
• Well-solvable cases of the QAP with block-structured matrices