Minimizing Weighted Flow Time

An important objective function in the scheduling literature is to minimize the sum of weighted flow times. We are given a set of jobs, where each job is characterized by a release time, a processing time, and a weight. Our goal is to find a preemptive schedule on a single machine that minimizes the sum of the weighted flow times of the jobs, where the flow time of a job is the time between its completion time and its release time. In their breakthrough result, Batra, Garg, and Kumar [FOCS 2018] found the first pseudopolynomial-time constant-factor approximation algorithm for the problem, which was turned into a polynomial-time algorithm by Feige, Kulkarni, and Li [SODA 2019]. The resulting approximation ratio is a (not explicitly stated) constant which is at least 10000. In this paper we improve this to a PTAS. The algorithm by Batra et al. reduces the problem to Demand MultiCut on trees and solves the resulting instances via LP-rounding and a dynamic program. Instead, we first reduce the problem to a (different) geometric problem while losing only a factor 1 + ϵ, and then solve its resulting instances exactly by a dynamic program. In particular, our reduction ensures certain structural properties, due to which we do not need LP-rounding techniques.