[uw.cs.grad] ICR Colloquium on Mar. 7, 1990, 3:30 p.m., in DC 1302. Dr. Henry Wolkowicz, Combinatorics and Optimization will speak on "Improving Bounds for the Quadratic Assignment Problem".

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.