## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 578-598 |

Number of pages | 21 |

Journal | Mathematics of Operations Research |

Volume | 49 |

Issue number | 1 |

DOIs | |

State | Published - Feb 2024 |

## Keywords

- approximation algorithm
- linear programming relaxation
- min-sum set cover
- precedence constraints
- scheduling