Benutzer: Gast  Login
Titel:

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

Dokumenttyp:
Zeitschriftenaufsatz
Autor(en):
Happach, Felix; Schulz, Andreas S.
Nicht-TUM Koautoren:
ja
Kooperation:
national
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...     »
Intellectual Contribution:
Discipline-based Research
Zeitschriftentitel:
Mathematics of Operations Research
Journal gelistet in FT50 Ranking:
nein
Jahr:
2023
Band / Volume:
49
Jahr / Monat:
2024-02
Heft / Issue:
1
Seitenangaben Beitrag:
578–598
Volltext / DOI:
doi:10.1287/moor.2023.1368
Verlag / Institution:
Institute for Operations Research and the Management Sciences (INFORMS)
E-ISSN:
0364-765X1526-5471
Eingereicht (bei Zeitschrift):
06.12.2019
Angenommen (von Zeitschrift):
29.10.2022
Publikationsdatum:
23.05.2023
Urteilsbesprechung:
0
Key publication:
Nein
Peer reviewed:
Ja
commissioned:
not commissioned
Technology:
Nein
Interdisziplinarität:
Nein
Leitbild:
;
Ethics und Sustainability:
Nein
 BibTeX