  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.
