Precedence-Constrained Scheduling and Min-Sum Set Cover
2020
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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
39
References
1
Citations
NaN
KQI