Simple Approximation Algorithms for Minimizing the Total Weighted Completion Time of Precedence-Constrained Jobs

Sven Jäger, Philipp Warode

We consider the precedence-constrained scheduling problem to minimize the total weighted completion time. For a single machine several $2$-approximation algorithms are known, which…