1 Search Results for "Rasmussen, Anna Rodriguez"

(In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling

Authors: Marten Maack, Simon Pukrop, and Anna Rodriguez Rasmussen

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

We consider variants of the restricted assignment problem where a set of jobs has to be assigned to a set of machines, for each job a size and a set of eligible machines is given, and the jobs may only be assigned to eligible machines with the goal of makespan minimization. For the variant with interval restrictions, where the machines can be arranged on a path such that each job is eligible on a subpath, we present the first better than 2-approximation and an improved inapproximability result. In particular, we give a (2-1/24)-approximation and show that no better than 9/8-approximation is possible, unless P=NP. Furthermore, we consider restricted assignment with R resource restrictions and rank D unrelated scheduling. In the former problem, a machine may process a job if it can meet its resource requirements regarding R (renewable) resources. In the latter, the size of a job is dependent on the machine it is assigned to and the corresponding processing time matrix has rank at most D. The problem with interval restrictions includes the 1 resource variant, is encompassed by the 2 resource variant, and regarding approximation the R resource variant is essentially a special case of the rank R+1 problem. We show that no better than 3/2, 8/7, and 3/2-approximation is possible (unless P=NP) for the 3 resource, 2 resource, and rank 3 variant, respectively. Both the approximation result for the interval case and the inapproximability result for the rank 3 variant are solutions to open challenges stated in previous works. Lastly, we also consider the reverse objective, that is, maximizing the minimal load any machine receives, and achieve similar results.

Cite as

Marten Maack, Simon Pukrop, and Anna Rodriguez Rasmussen. (In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 77:1-77:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

  author =	{Maack, Marten and Pukrop, Simon and Rasmussen, Anna Rodriguez},
  title =	{{(In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{77:1--77:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.77},
  URN =		{urn:nbn:de:0030-drops-170152},
  doi =		{10.4230/LIPIcs.ESA.2022.77},
  annote =	{Keywords: Scheduling, Restricted Assignment, Approximation, Inapproximability}
  • Refine by Author
  • 1 Maack, Marten
  • 1 Pukrop, Simon
  • 1 Rasmussen, Anna Rodriguez

  • Refine by Classification
  • 1 Theory of computation → Problems, reductions and completeness
  • 1 Theory of computation → Scheduling algorithms

  • Refine by Keyword
  • 1 Approximation
  • 1 Inapproximability
  • 1 Restricted Assignment
  • 1 Scheduling

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022