Linearizable special cases of the QAP

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

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)
1 Downloads (Pure)


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
Issue number3
Publication statusPublished - 1 Apr 2016


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


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

Cite this