Approximation Algorithms and Linear Programming Relaxations for Scheduling Problems Related to Min-Sum Set Cover.

This article focuses on single-machine scheduling problems with AND/OR-precedence constraints that generalize the min-sum set cover problem and its variants. It presents new approximation algorithms based on time-indexed linear programming (LP) relaxations and randomized α-point scheduling, achieving a 2Δ-approximation for instances with processing times in {0,1} (where Δ is the maximum number of OR-predecessors of any job) and extending to arbitrary processing times with a (2Δ + ε)-approximation. The work also introduces a 4-approximation algorithm for the all-but-one generalized min-sum set cover problem, a special case where each job requires all but one of its predecessors to be completed, and provides the first constant-factor approximation for scheduling with bipartite OR-precedence constraints. Additionally, the authors analyze other LP relaxations—linear ordering and completion-time formulations—showing that these exhibit linear integrality gaps in the presence of OR-precedence constraints, indicating limitations of these approaches. The paper further establishes NP-hardness results for scheduling with bipartite OR-precedence constraints under certain processing time and weight restrictions.