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.