Optimization for scheduling and beyond, a set covering view of scheduling

Speaker: 

Jatin Batra

Affiliation: 

CWI Amsterdam, Netherlands

Time: 

Thursday, 10 December 2020, 16:00 to 17:00

Organisers: 

Scheduling provides an interesting context for optimization methods. This talk is about how a set covering viewpoint can provide powerful insights into scheduling in many settings - minimizing response times on a single machine, heterogenous scheduling on multiple machines, diversification in information retrieval etc. Along the way, I will also illustrate connections and improvements to classic set covering problems in the context of knapsacks, geometric set cover and minimum-cuts. Along the way, I will show how Chernoff bounds can be improved for lower tails of Bernoulli distributions.