Campuses:

Complexity Aspects of SDP Relaxations of Polynomial Optimization Problems

Wednesday, January 17, 2007 - 9:30am - 10:20am
EE/CS 3-180
Markus Schweighofer (Universität Konstanz)
We discuss complexity aspects of Lasserre's sequence
of SDP relaxations of a given
polynomial optimization problem. As a special example where a
lot is known, we
consider the MAXCUT problem. The following topics should be
covered:

- the moment problem and convergence to unique minimizers,

- speed of convergence to the optimal value,

- Scheiderers result on stability and the moment problem,

- the approximability result of Goemans and Williamson for
MAXCUT, and

- the inapproximability result of Khot, Kindler, Mossel and
O'Donnell for MAXCUT.
MSC Code: 
35C11