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.ICALP.2021.42
URN: urn:nbn:de:0030-drops-141116
URL: https://drops.dagstuhl.de/opus/volltexte/2021/14111/
Go to the corresponding LIPIcs Volume Portal


Buchem, Moritz ; Rohwedder, Lars ; Vredeveld, Tjark ; Wiese, Andreas

Additive Approximation Schemes for Load Balancing Problems

pdf-format:
LIPIcs-ICALP-2021-42.pdf (0.6 MB)


Abstract

We formalize the concept of additive approximation schemes and apply it to load balancing problems on identical machines. Additive approximation schemes compute a solution with an absolute error in the objective of at most ε h for some suitable parameter h and any given ε > 0. We consider the problem of assigning jobs to identical machines with respect to common load balancing objectives like makespan minimization, the Santa Claus problem (on identical machines), and the envy-minimizing Santa Claus problem. For these settings we present additive approximation schemes for h = p_{max}, the maximum processing time of the jobs.
Our technical contribution is two-fold. First, we introduce a new relaxation based on integrally assigning slots to machines and fractionally assigning jobs to the slots. We refer to this relaxation as the slot-MILP. While it has a linear number of integral variables, we identify structural properties of (near-)optimal solutions, which allow us to compute those in polynomial time. The second technical contribution is a local-search algorithm which rounds any given solution to the slot-MILP, introducing an additive error on the machine loads of at most ε⋅ p_{max}.

BibTeX - Entry

@InProceedings{buchem_et_al:LIPIcs.ICALP.2021.42,
  author =	{Buchem, Moritz and Rohwedder, Lars and Vredeveld, Tjark and Wiese, Andreas},
  title =	{{Additive Approximation Schemes for Load Balancing Problems}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{42:1--42:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14111},
  URN =		{urn:nbn:de:0030-drops-141116},
  doi =		{10.4230/LIPIcs.ICALP.2021.42},
  annote =	{Keywords: Load balancing, Approximation schemes, Parallel machine scheduling}
}

Keywords: Load balancing, Approximation schemes, Parallel machine scheduling
Collection: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue Date: 2021
Date of publication: 02.07.2021


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