TY - GEN

T1 - A PTAS for Minimizing Weighted Flow Time on a Single Machine

AU - Armbruster, Alexander

AU - Rohwedder, Lars

AU - Wiese, Andreas

N1 - Publisher Copyright:
© 2023 ACM.

PY - 2023/6/2

Y1 - 2023/6/2

N2 - 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. The currently best known polynomial time algorithm for the problem is a (2+")-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+")-approximation algorithm for weighted flow time on a single machine. We use a reduction of the problem to a geometric covering problem, which was introduced in the mentioned (2+")-approximation algorithm and which loses only a factor of 1+"in the approximation ratio. However, unlike that algorithm, we solve the resulting instances of the covering problem exactly, rather than losing a factor 2+". Key for this is to identify and exploit structural properties of instances of that problem covering problem which arise in the reduction from weighted flow time.

AB - 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. The currently best known polynomial time algorithm for the problem is a (2+")-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+")-approximation algorithm for weighted flow time on a single machine. We use a reduction of the problem to a geometric covering problem, which was introduced in the mentioned (2+")-approximation algorithm and which loses only a factor of 1+"in the approximation ratio. However, unlike that algorithm, we solve the resulting instances of the covering problem exactly, rather than losing a factor 2+". Key for this is to identify and exploit structural properties of instances of that problem covering problem which arise in the reduction from weighted flow time.

KW - PTAS

KW - dynamic programming

KW - flow time

KW - scheduling

UR - http://www.scopus.com/inward/record.url?scp=85163086450&partnerID=8YFLogxK

U2 - 10.1145/3564246.3585146

DO - 10.1145/3564246.3585146

M3 - Conference contribution

AN - SCOPUS:85163086450

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1335

EP - 1344

BT - STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing

A2 - Saha, Barna

A2 - Servedio, Rocco A.

PB - Association for Computing Machinery

T2 - 55th Annual ACM Symposium on Theory of Computing, STOC 2023

Y2 - 20 June 2023 through 23 June 2023

ER -