Theory Seminar

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

Lars RohwedderMaastricht University
WHERE:
3725 Beyster Building
SHARE:

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.

Organizer

Greg Bodwin

Organizer

Euiwoong Lee