An important objective in 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. The currently best known polynomial time algorithm for the problem is a (2+eps)-approximation by Rohwedder and Wiese [STOC 2021] which builds on the prior break-through result by Batra, Garg, and Kumar [FOCS 2018] who found the first pseudo-polynomial time constant factor approximation algorithm for the problem, and on the result by Feige, Kulkarni, and Li [SODA 2019] who turned the latter into a polynomial time algorithm. However, it remains open whether the problem admits a PTAS. We answer this question in the affirmative and present a polynomial time (1+eps)-approximation algorithm for weighted flow time on a single machine. We rely on a reduction of the problem to a geometric covering problem, which was introduced in the mentioned (2+eps)-approximation algorithm, losing a factor 1+eps in the approximation ratio. However, unlike that algorithm, we solve the resulting instances of this problem exactly, rather than losing a factor 2+eps. Key for this is to identify and exploit structural properties of instances of the geometric covering problem which arise in the reduction from weighted flow time.

Thanks. We have received your report. If we find this content to be in
violation of our guidelines,
we will remove it.

Ok