  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$ has an integral processing time $p_j$, and there is
a nondecreasing, nonnegative cost function $f_j(C_{j})$ that specifies the cost
of finishing $j$ at time $C_{j}$; the objective is to minimize $\sum_{j=1}^n
f_j(C_j)$. Bansal \& Pruhs recently gave the first constant approximation
algorithm with a performance guarantee of 16. We improve on this result by
giving a primal-dual pseudo-polynomial-time algorithm based on the recently
introduced knapsack-cover inequalities. The algorithm finds a schedule of cost
at most four times the constructed dual solution. Although we show that this
bound is tight for our algorithm, we leave open the question of whether the
integrality gap of the LP is less than 4. Finally, we show how the technique
can be adapted to yield, for any $\epsilon >0$, a $(4+\epsilon )$-approximation
algorithm for this problem.
