A (2 + epsilon)-approximation algorithm for preemptive weighted flow time on a single machine.

Abstract:  In a recent breakthrough in scheduling, Batra, Garg, and Kumar gave the first constant approximation algorithm for minimizing the sum of weighted flow times. Wiese and I (STOC’21) managed to improve this large unspecified constant to 2 + epsilon. I will give a very graphic presentation of the algorithmic techniques behind this.

Posted on Apr 12, 2021 in ACGO, Seminars