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

Jatin Batra
Kavitha Telikepalli
Thursday, 10 Dec 2020, 16:00 to 17:00
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.