CWI Amsterdam, Netherlands
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.