title:
 Semidefinite Relaxations for Hard Combinatorial Problems
    Henry Wolkowicz
    Dept. Comb. and Opt.
    University of Waterloo

Abstract:
Many hard combinatorial problems can be modelled 
as the minimization (or maximization) of a quadratic function subject to
quadratic constraints, denoted QQP.
These models are nonconvex in general; so
finding a global solution is itself a very hard problem.
We look at Lagrangian relaxations for these QQPs. These Lagrangian
relaxations are equivalent to semidefinite programming
relaxations, i.e. to the
minimization of a linear function of symmetric matrices subject to
linear and semidefinite constraints, denoted SDP. These relaxations are
convex problems that can be solved efficiently using interior-point
methods. Moreover, the bounds they provide are surprisingly tight.
We examine several instances: 
the max-cut; quadratic assignment; and graph partitioning problems.