Approximation Algorithms and Linear Programming Relaxations for Scheduling Problems Related to Min-Sum Set Cover
Mathematics of Operations Research · 2024-02 · 49 (1) · 578-598
DOI: 10.1287/moor.2023.1368 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics of Operations Research, 2024-02. Verfasst von Felix Happach und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 38 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
APA
Happach, F., & Schulz, A. S. (2024). Approximation Algorithms and Linear Programming Relaxations for Scheduling Problems Related to Min-Sum Set Cover. Mathematics of Operations Research, 49(1), 578-598. https://doi.org/10.1287/moor.2023.1368
Vancouver
Happach F, Schulz AS. Approximation Algorithms and Linear Programming Relaxations for Scheduling Problems Related to Min-Sum Set Cover. Mathematics of Operations Research. 2024;49(1):578-598. doi:10.1287/moor.2023.1368
BibTeX
@article{Happach2024,
author = {Happach, Felix and Schulz, Andreas S.},
title = {Approximation Algorithms and Linear Programming Relaxations for Scheduling Problems Related to Min-Sum Set Cover},
journal = {Mathematics of Operations Research},
year = {2024},
volume = {49},
number = {1},
pages = {578--598},
doi = {10.1287/moor.2023.1368}
}
EUVIMED