Campuses:

Polynomial solutions

Wednesday, January 17, 2007 - 9:30am - 10:20am
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
Subscribe to RSS - Polynomial solutions