ylkingsbury@watdragon.waterloo.edu (Yvonne Kingsbury) (03/02/90)
The University of Waterloo 200 University Avenue Waterloo, Ontario The Institute for Computer Research (ICR) Presents a Colloquium on Improving Bounds for the Quadratic Assignment Problem by Dr. Henry Wolkowicz of Department of Combinatorics and Optimization, University of Waterloo Wednesday, March 7, 1990 3:30 p.m. William G. Davis Computer Research Centre, Room 1302 ABSTRACT The quadratic assignment problem, denoted QAP, can be formulated as follows: given the three n by n matrices A,B,C, find the per- mutation matrix X which minimizes the trace min tr(C + AXB sup t )X sup t . X mo PI This problem arises in e.g. facility location problems where we are given the distance matrix A, the flow matrix B, and the loca- tion cost matrix C. We study approximate solution techniques which result in lower bounds for QAP. In particular, we consider eigenvalue decomposition approaches for the quadratic part of QAP. Various bounding techniques are presented and compared. Everyone is welcome. Refreshments served.