A PTAS for Minimizing Weighted Flow Time on a Single Machine

Alexander Armbruster, Lars Rohwedder, Andreas Wiese

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationSTOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing
EditorsBarna Saha, Rocco A. Servedio
PublisherAssociation for Computing Machinery
Pages1335-1344
Number of pages10
ISBN (Electronic)9781450399135
DOIs
StatePublished - 2 Jun 2023
Event55th Annual ACM Symposium on Theory of Computing, STOC 2023 - Orlando, United States
Duration: 20 Jun 202323 Jun 2023

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference55th Annual ACM Symposium on Theory of Computing, STOC 2023
Country/TerritoryUnited States
CityOrlando
Period20/06/2323/06/23

Keywords

  • PTAS
  • dynamic programming
  • flow time
  • scheduling

Fingerprint

Dive into the research topics of 'A PTAS for Minimizing Weighted Flow Time on a Single Machine'. Together they form a unique fingerprint.

Cite this