Verimag

Seminar details

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.




Contact | Site Map | Site powered by SPIP 3.0.26 + AHUNTSIC [CC License]

info visites 915574