Monaldo Mastrolilli: High Degree Sum of Squares Proofs/Hierarchy for 0/1 Problems (LIG/VERIMAG seminar)

Prof. Monaldo Mastrolilli, IDSIA Lugano

http://people.idsia.ch/~monaldo/

The Lasserre/Sum-of-Squares (SOS) hierarchy is a systematic procedure for constructing a sequence of increasingly tight semidefinite relaxations. It is known that the hierarchy converges to the 0/1 polytope in n levels and captures the convex relaxations used in the best available approximation algorithms for a wide variety of optimization problems.
In this talk I will give a gentle introduction of the SOS framework for 0/1 problems from a more general point of view.
I will point it out that this more general definition is needed for certain class of problems, it removes some of the weakness of the standard SOS approach.