**Date & Time:** 13th October, 2010; 11.30-12.30

**Venue:** Ramanujan Hall

**Title:** Linearization of QAP and QTSP: Characterizations and Efficient
Algorithms

**Speaker:** Professor Santosh N. Kabadi,
Faculty of Business Administration,
University of New Brunswick
Fredericton, NB, Canada

**Abstract:** An instance of Quadratic Assignment Problem (QAP) with cost matrix Q
is said to be linearizable if there exists an instance of the Linear
Assignment Problem (LAP) with cost matrix C such that for each
assignment, the QAP and LAP objective function values are identical.
We give a necessary and sufficient condition for a given instance of
QAP to be linearizable and develop an O(n^4) algorithm to solve the
linearization problem. For the special case of the Koopmans-Beckmann
QAP our algorithm runs in O(n^2) time. We also consider the
linearization problem for the Quadratic Traveling Salesman Problem
(QTSP) and establish necessary and sufficient conditions for
linearizability that lead to an O(n^4) algorithm.