A 4-approximation for scheduling on a single machine with general cost function

Julián Mestre, José Verschae

We consider a single machine scheduling problem that seeks to minimize a generalized cost function: given a subset of jobs we must order them so as to minimize $\sum f_j(C_j)$, whe…