EUVIMEDEUVIMED entdecken
Crossref

Approximation Algorithms and Linear Programming Relaxations for Scheduling Problems Related to Min-Sum Set Cover

Felix Happach, Andreas S. Schulz

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →