Linearizable special cases of the QAP

E. Çela, V.G. Deineko, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)
1 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)1269-1279
Number of pages11
JournalJournal of Combinatorial Optimization
Volume31
Issue number3
DOIs
Publication statusPublished - 1 Apr 2016

Keywords

  • Combinatorial optimization
  • Computational complexity
  • Linear assignment problem
  • Quadratic assignment problem

Fingerprint Dive into the research topics of 'Linearizable special cases of the QAP'. Together they form a unique fingerprint.

Cite this