Precedence-Constrained Scheduling and Min-Sum Set Cover: (Extended Abstract)

We consider a single-machine scheduling problem with bipartite AND/OR-constraints that is a natural generalization of (precedence-constrained) min-sum set cover. For min-sum set cover, Feige, Lovàsz and Tetali [15] showed that the greedy algorithm has an approximation guarantee of 4, and obtaining a better approximation ratio is NP-hard. For precedence-constrained min-sum set cover, McClintock, Mestre and Wirth [30] proposed an algorithm, where m is the number of sets. They also showed that obtaining an algorithm with performance is impossible, assuming the hardness of the planted dense subgraph problem. The more general problem examined here is itself a special case of scheduling AND/OR-networks on a single machine, which was studied by Erlebach, Kääb and Möhring [13]. Erlebach et al. proposed an approximation algorithm whose performance guarantee grows linearly with the number of jobs, which is close to best possible, unless P = NP. For the problem considered here, we give a new LP-based approximation algorithm. Its performance ratio depends only on the maximum number of OR-predecessors of any one job. In particular, in many relevant instances, it has a better worst-case guarantee than the algorithm by McClintock et al., and it also improves upon the algorithm by Erlebach et al. (for the special case considered here). Yet another important generalization of min-sum set cover is generalized min-sum set cover, for which a 12.4-approximation was derived by Im, Sviridenko and Zwaan [23]. Im et al. conjecture that generalized min-sum set cover admits a 4-approximation, as does min-sum set cover. In support of this conjecture, we present a 4-approximation algorithm for another interesting special case, namely when each job requires that no less than all but one of its predecessors are completed before it can be processed.