Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

On Some Easy Problems That Are Hard for the Lasserre Hierarchy

Hausdorff Center for Mathematics via YouTube

Overview

Explore a 28-minute lecture on the Lasserre hierarchy and its limitations in solving certain optimization problems. Gain insights into lower bound results for this hierarchy, including characterizations of problems with integrality gaps at high levels. Learn about a scheduling problem solvable in O(n log n) time that exhibits an unbounded integrality gap in the Lasserre hierarchy. Discover how symmetry in problem formulations can simplify the analysis of positive semidefiniteness. Examine a concise proof of the Grigoriev/Laurent lower bound for the integer cut polytope of complete graphs. This talk, presented by Monaldo Mastrolilli at the Hausdorff Center for Mathematics, covers joint work with A. Kurpisz and S. Leppanem.

Syllabus

Monaldo Mastrolilli: On some easy problems that are hard for the Lasserre hierarchy

Taught by

Hausdorff Center for Mathematics

Reviews

Start your review of On Some Easy Problems That Are Hard for the Lasserre Hierarchy

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.