论文标题
与Min-sum设置有关的调度问题的近似算法和LP放松
Approximation Algorithms and LP Relaxations for Scheduling Problems Related to Min-Sum Set Cover
论文作者
论文摘要
我们考虑了单机计划问题，这些问题是Min-sum设置覆盖问题和Min-sum顶点覆盖问题的自然概括或变化。对于这些问题，我们提供了新的近似算法。这些算法中的一些依赖于时间指数的LP松弛。我们展示了Alpha点调度的变体如何导致最著名的近似值，其中包括一个有趣的特殊情况，即所谓的广义Min-sum套装问题的保证。我们还明确说明了Min-sum集盖的贪婪算法与Sidney Decomposition的概念，用于预先约束的单机械调度，并展示这如何导致具有所谓的Biptite Orpartite Orperdite Orpredence Constraints的单机械调度的4-附属算法。
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.
