User: Guest  Login
Title:

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

Document type:
Zeitschriftenaufsatz
Author(s):
Happach, Felix; Schulz, Andreas S.
Non-TUM Co-author(s):
ja
Cooperation:
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
Journal title:
Mathematics of Operations Research
Journal listet in FT50 ranking:
nein
Year:
2023
Journal volume:
49
Year / month:
2024-02
Journal issue:
1
Pages contribution:
578–598
Fulltext / DOI:
doi:10.1287/moor.2023.1368
Publisher:
Institute for Operations Research and the Management Sciences (INFORMS)
E-ISSN:
0364-765X1526-5471
Submitted:
06.12.2019
Accepted:
29.10.2022
Date of publication:
23.05.2023
Judgement review:
0
Key publication:
Nein
Peer reviewed:
Ja
Commissioned:
not commissioned
Technology:
Nein
Interdisciplinarity:
Nein
Mission statement:
;
Ethics and Sustainability:
Nein
 BibTeX