  We consider single-machine scheduling problems that are natural
generalizations or variations of the min-sum set cover problem and the min-sum
vertex cover problem. For each of these problems, we give new approximation
algorithms. Some of these algorithms rely on time-indexed LP relaxations. We
show how a variant of alpha-point scheduling leads to the best-known
approximation ratios, including a guarantee of 4 for an interesting special
case of the so-called generalized min-sum set cover problem. We also make
explicit the connection between the greedy algorithm for min-sum set cover and
the concept of Sidney decomposition for precedence-constrained single-machine
scheduling, and show how this leads to a 4-approximation algorithm for
single-machine scheduling with so-called bipartite OR-precedence constraints.
