A PTAS for minimizing weighted flow time on a single machine

DOI10.1145/3564246.3585146MaRDI QIDQ6499308

Alexander Armbruster, Lars Rohwedder, Andreas Wiese

Publication date: 8 May 2024

zbMATH Keywords

schedulingdynamic programmingflow timePTAS

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for average stretch scheduling
• Approximation schemes for preemptive weighted flow time
• Server scheduling in the L _p norm
• Minimizing weighted flow time
• Fixed-Parameter Approximation Schemes for Weighted Flowtime.
• Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time
• The Geometry of Scheduling
• Algorithms for minimizing weighted flow time
• A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time
• LATIN 2004: Theoretical Informatics
• A (2 + ε )-approximation algorithm for preemptive weighted flow time on a single machine

This page was built for publication: A PTAS for minimizing weighted flow time on a single machine