Minimizing Weighted Flow Time
Journal of the ACM · 30.06.2026 · 73 (3) · 1-23
DOI: 10.1145/3802582 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 16.06.2026. Verfasst von Alexander Armbruster und 2 weiteren Autor:innen. Die Arbeit nennt 23 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Dutch Research Council (NWO) project “The Twilight Zone of Efficiency: Optimality of Quasi-Polynomial Time Algorithms”.
Abstract (Originalsprache)
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 10,000. In this article, we improve this to a PTAS. 1 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 + \varepsilon\) , 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.
Förderung
- Dutch Research Council (NWO) project “The Twilight Zone of Efficiency: Optimality of Quasi-Polynomial Time Algorithms”
Zitieren
APA
Armbruster, A., Rohwedder, L., & Wiese, A. (2026). Minimizing Weighted Flow Time. Journal of the ACM, 73(3), 1-23. https://doi.org/10.1145/3802582
Vancouver
Armbruster A, Rohwedder L, Wiese A. Minimizing Weighted Flow Time. Journal of the ACM. 2026;73(3):1-23. doi:10.1145/3802582
BibTeX
@article{Armbruster2026,
author = {Armbruster, Alexander and Rohwedder, Lars and Wiese, Andreas},
title = {Minimizing Weighted Flow Time},
journal = {Journal of the ACM},
year = {2026},
volume = {73},
number = {3},
pages = {1--23},
doi = {10.1145/3802582}
}
EUVIMED