A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems

Maurice Cheung, Julián Mestre, David B. Shmoys +1

We consider the following single-machine scheduling problem, which is often denoted $1||\sum f_j$: we are given $n$ jobs to be scheduled on a single machine, where each job $j$ h…