EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Minimizing Weighted Flow Time

Alexander Armbruster, Lars Rohwedder, Andreas Wiese

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”.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →