Talk: Scheduling with Communication Delays

LIVE STREAM: https://uwmadison.zoom.us/j/92796936341?pwd=WCtxazhOSGV2ZzBremtmdW03WDliZz09

Abstract: I will begin by discussing progress on scheduling with communication delays. In this setting, the input of one job might depend on the output of another, and further, if these jobs are scheduled on different machines, a delay must pass between their execution times. Whether constant factor approximation algorithms exist in this setting was one of the biggest open problems in scheduling theory. We make enormous progress on understanding this model by (1) finding polylog approximations algorithms when the delay is uniform between dependent jobs and (2) proving super-constant hardness when the delay is non-uniform between dependent jobs.

These results for communication delays fall into the category of ``worst-case optimization”, which is the traditional metric for algorithm evaluation in theory. I will then discuss the importance of theoreticians balancing worst-case optimization with ``beyond worst-case optimization”, some examples of my recent work in this space, and my future plans for pushing scheduling (and more broadly combinatorial optimization) with beyond worst-case optimization models.

Bio: Sami Davies is a post-doctoral researcher at Northwestern University, and she is also a member of the 2021 cohort of NSF Computing Innovation Fellows. Sami earned her PhD from the University of Washington in 2021, where she was advised by Thomas Rothvoss. Her research is broadly in theoretical computer science; much of her work is on scheduling problems, though a recent focus for her research are models that go beyond worst-case optimization.