Seminar Room, ground floor (Building IMAG)
16 February 2017 - 11h00
High Degree Sum of Squares Proofs/Hierarchy for 0/1 Problems
by Mastrolilli Monaldo from IDSIA Lugano
Abstract: 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 e removes some of the weakness of the standard SOS approach.
