Sami Davies : Scheduling with Communication Delays via LP Hierarchies and Clustering

Posted by Karoline Dubin , part of the Computer Science Theory Seminar.

At

Oct. 20, 2021, 3 p.m.

In

636 SEO

Abstract

Ever have a linear program with an integrality gap that you'd like to beat and think "darn, I can't come up with a constraint that gets rid of this integrality gap instance!"? Well, LP hierarchies may be the tool for you! They provide a systematic way to add constraints and variables to an LP, thus strengthening it. In this talk, I will (1) give intuition behind the Sherali-Adams hierarchy and (2) exemplify the usefulness of the Sherali-Adams hierarchy by applying it to (what was) one of the biggest open questions in scheduling theory.