Precedence-Constrained Scheduling and Min-Sum Set Cover
Precedence-Constrained Scheduling and Min-Sum Set Cover
复制标题
优先级约束调度和最小和集覆盖
DOI：
10.1007/978-3-030-39479-0_12
复制
发表时间：
2019
期刊：
影响因子：
1.1
通讯作者：
Andreas S. Schulz
中科院分区：
文献类型：
--
作者：
Felix Happach;Andreas S. Schulz
我们考虑一个带有二部AND/OR约束的单机排序问题，它是(优先约束的)最小和集覆盖的自然推广。对于最小和集覆盖，Feige，Lovasz和Tetali[15]证明了贪婪算法具有4的逼近保证，并且获得更好的逼近比是NP难的。对于优先约束的最小和集合覆盖，McClintock，Mestre和Wirth在[30]中提出了一个O(Sqrt{m})-近似算法，其中m是集合的个数。他们还证明了，假设所种植的稠密子图问题的难度很大，得到一个性能为O(m^{1/12-varepsilon})的算法是不可能的。
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, Lovasz 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 \(O(\sqrt{m})\)-approximation algorithm, where m is the number of sets. They also showed that obtaining an algorithm with performance \(O(m^{1/12-\varepsilon })\) is impossible, assuming the hardness of the planted dense subgraph problem.