Approximation Algorithms and Linear Programming Relaxations for Scheduling Problems Related to Min-Sum Set Cover
研究了最小和集合覆盖问题的自然推广或变体的单机调度问题，提出了新的近似算法，其中一些基于时间索引线性规划松弛，并给出了最佳已知近似比。
We consider single-machine scheduling problems that are natural generalizations or variations of the min-sum set-cover problem. For these scheduling problems, we give new approximation algorithms. Some of these algorithms rely on time-indexed linear programming relaxations. We show how a variant of alpha-point scheduling leads to the best known approximation ratios, including a guarantee of four 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. Funding: This work has been supported by the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research.