Computer Science Theory Seminar
Sami Davies
Northwestern
Scheduling with Communication Delays via LP Hierarchies and Clustering
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.
Wednesday October 20, 2021 at 3:00 PM in 636 SEO