Lars Rohwedder: Simpler and stronger approximation algorithms for flow time scheduling

PASSCODE: 430018

Flow time measures the duration from release until completion of a job. It is one of the most natural, but also most notorious objectives in scheduling. A long-standing open question in the field was to obtain a polynomial time constant approximation for total weighted flow time on a single machine. This was recently solved in a combination of a tour-de-force of Batra, Garg, and Kumar and a clever instance reduction by Feige, Kulkarni, and Li. I will present a simpler algorithm from joint work with Armbruster and Wiese and (close to) a full, self-contained proof of the result. Afterwards, I will briefly discuss settings with several parallel machines and, in particular, recent joint work with Bansal and Svensson that points out connections to Discrepancy theory.