Tata Institute of Fundamental Research

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

STCS Seminar
Speaker: Jatin Batra (CWI Amsterdam, Netherlands)
Organiser: Kavitha Telikepalli
Date: Thursday, 10 Dec 2020, 16:00 to 17:00

(Scan to add to calendar)
Abstract:  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.