License:
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2021.53
URN: urn:nbn:de:0030-drops-146344
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14634/
Jansen, Klaus ;
Rau, Malin
Closing the Gap for Single Resource Constraint Scheduling
Abstract
In the problem called single resource constraint scheduling, we are given m identical machines and a set of jobs, each needing one machine to be processed as well as a share of a limited renewable resource R. A schedule of these jobs is feasible if, at each point in the schedule, the number of machines and resources required by jobs processed at this time is not exceeded. It is NP-hard to approximate this problem with a ratio better than 3/2. On the other hand, the best algorithm so far has an absolute approximation ratio of 2+ε. In this paper, we present an algorithm with absolute approximation ratio (3/2+ε), which closes the gap between inapproximability and best algorithm with exception of a negligible small ε.
BibTeX - Entry
@InProceedings{jansen_et_al:LIPIcs.ESA.2021.53,
author = {Jansen, Klaus and Rau, Malin},
title = {{Closing the Gap for Single Resource Constraint Scheduling}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {53:1--53:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-204-4},
ISSN = {1868-8969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14634},
URN = {urn:nbn:de:0030-drops-146344},
doi = {10.4230/LIPIcs.ESA.2021.53},
annote = {Keywords: resource constraint scheduling, approximation algorithm}
}
Keywords: |
|
resource constraint scheduling, approximation algorithm |
Collection: |
|
29th Annual European Symposium on Algorithms (ESA 2021) |
Issue Date: |
|
2021 |
Date of publication: |
|
31.08.2021 |