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/
Go to the corresponding LIPIcs Volume Portal

Jansen, Klaus ; Rau, Malin

Closing the Gap for Single Resource Constraint Scheduling

pdf-format:
LIPIcs-ESA-2021-53.pdf (0.8 MB)

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI