Talk
Flow Time Scheduling with Uncertain Processing Time
We consider the problem of online scheduling to minimize unweighted and weighted flow time. The existing algorithms for these problems require exact knowledge of the processing time of each job. This assumption is crucial for them but very rarely holds in real-life scenarios. We present competitive algorithms (the competitive ratio is a function of the distortion) for unweighted flow time that do not require knowledge of the distortion in advance. For the weighted flow time we present competitive algorithms but, in this case, we need to know (an upper bound on) the distortion in advance. This is joint work with Stefano Leonardi, Eldad Peretz and Noam Touitou based on papers that appeared in STOC 21, SODA 2022 and ISAAC 2022.